Chapter 2 Representing and Manipulating Information

2020-03-25在自己博客园搬运过来…

Homework Problems

2.57

void show_short(short x)
{
    show_bytes((byte_pointer) &x, sizeof(short));
}

void show_long(long x)
{
    show_bytes((byte_pointer) &x, sizeof(long));
}

void show_double(double x)
{
    show_bytes((byte_pointer) &x, sizeof(double));
}

2.58

int is_little_endian()
{
    int a = 1;
    　　/*
    &a: 取a的地址

    (char*)&a: 将a的地址所在的位置的值视为字符型指针的地址

    *(char*)&a: 取a所在地址的第0个字节的值作为一个char类型返回

    　　*/
    return *(char*)&a;
}

2.59

result = (x & 0xFF) | (y & (~0xFF));

2.60

unsigned replace_byte(unsigned x, int i, unsigned char b)
{
    int j;
    unsigned char c;

    j = 8 * i;
    b = b << j;
    c = ~(0xFF << j);
    return ((x & c) | b);
}

2.61

//A
bool result = !(x + 1);

//B
bool result = !x;

//C
bool result = !(~(x | (~0xFF)));

//D
bool result = !(~(x >> ((sizeof(int) - 1) << 3)));

2.62

bool shifts_are_arithmetic()
{
    /*这里不能写x = 0xFFFFFFFF,因为int不一定是32位的*/
    int x = -1;
    return !(x ^ (x >> ((sizeof(int)));
}

2.63

unsigned srl(unsigned x, int k)
{
    /*Perform shift arithmetically*/
    unsigned xsra = (int)x >> k;
    int w = sizeof(int) << 3;
    unsigned y = 2 << (w - k - 1);
    return (y - 1) & xsra;
}

int sra(int x, int k)
{
    /*Perform shift logically*/
    int xsrl = (unsigned)x >> k;
    int w = sizeof(int) << 3;
    int y = -1 << (w - k - 1);
    int z = (~((xsrl & y) + y) & y) << 1;
    return xsrl | z;
}

2.64

int any_odd_one(unsigned x)
{
	return !(~(x | 0x55555555));
}

2.65

/*Return 1 when x contains an odd number of 1s; 0 otherwise. Assume w = 32*/
int odd_ones(unsigned x)
{
    x ^= x >> 1;
    x ^= x >> 2;
    x ^= x >> 4;
    x ^= x >> 8;
    x ^= x >> 16;
    return x & 1;
}

2.66

/*Generate mask indicating leftmost 1 in x. Assume w = 32
 *For example, 0xFF00->0x8000, and 0x6600->0x4000.
 *If x = 0, then return 0.
 */
int leftmost_one(unsigned x)
{
    x |= x << 1;
    x |= x << 2;
    x |= x << 4;
    x |= x << 8;
    x |= x << 16;
    return x ^ (x >> 1);
}

2.67

//A
Right shift, only with shift amounts between 0 and w - 1, and w is 32.

//B
int int_size_32()
{
    int set_msb = 1 << 31;
    int beyond_msb = 2 << 31;
    return set_msb && !beyond_msb;
}

//C
int int_size_16()
{
    int set_msb = 1 << 15;
    int beyond_msb = 2 << 15;
    return set_msb && !beyond_msb;
}

2.68

/*Mask with least significant n bits set to 1. Assume 1 <= n <= 32*/
int lower_one_mask(int n)
{
    unsigned x = 0xFFFFFFFF;
    return x >> (32 - n);
}

2.69

unsigned rotate_left(unsigned x, int n)
{
	return (x << n) | (x >> ((sizeof(int) << 3) - n));
}

2.70

/*Return 1 when x can be represented as an n_bit, 2's-complement number;
 *0 otherwise. Assume 1 <= n <= w*/
int fits_bits(int x, int n)
{
    return (x >> n == 0) || (~(x >> n) == 0);
}

2.71

//A
The type of return value of the function is unsigned int, but it needs signed int.

//B
int xbyte(packed_t word, int bytenum)
{
    return (int)((word << ((3 - bytenum) << 3)) >> 24);
}

2.72

A:
The type of the value of “maxbytes - sizeof(val)” is unsigned.
B:
if (maxbytes >= sizeof(val))

2.73

/*Addition that saturates to TMin or TMax*/
int saturating_add(int x, int y)
{
    int sum = x + y;
    int x_sign = x >> (w - 1);        //X的符号位
    int y_sign = y >> (w - 1);        //Y的符号位
    int sum_sign = sum >> (w - 1);    //Sum的符号位
    int pos_overflow = !x_sign && !y_sign && sum_sign;    //判断正溢出
    int neg_overflow = x_sign && y_sign && !sum_sign;    //判断负溢出
    int overflow = pos_overflow || neg_overflow;    //设置溢出位
    /*将溢出位设置扩展为位模式(全1或全0)*/
    overflow <<= (w - 1);
    overflow >>= (w - 1);
    /*根据是否溢出进行选择*/
    return (sum & ~overflow) + ((INT_MAX + !pos_overflow) & overflow);
}

2.74

/*Determine whether arguments can be subtracted without overflow*/
int tsub_ok(int x, int y)
{
    int sum = x - y;
    int x_sign = x >> (w - 1);        //X的符号位
    int y_sign = y >> (w - 1);        //Y的符号位
    int sum_sign = sum >> (w - 1);    //Sum的符号位
    int pos_overflow = !x_sign && y_sign && sum_sign;    //正溢出
    int neg_overflow = x_sign && !y_sign && !sum_sign;    //负溢出
    return !(pos_overflow || neg_overflow);
}

2.75

unsigned unsigned_high_prod(unsigned x, unsigned y)
{
    uint64_t msb_x = (uint64_t)x >> ((sizeof(x) << 3) - 1);
    uint64_t msb_y = (uint64_t)y >> ((sizeof(x) << 3) - 1);
    uint64_t goal = (int)x * (int)y + signed_high_prod(x, y) << (sizeof(int) << 3) + (x * msb_y + y + msb_x) << (sizeof(int) << 3) + (msb_x * msb_y) << (((sizeof(int) << 3) << 1) - 1) << 1;
    return goal >> (sizeof(int) << 3);
}

2.76

/*通过调用malloc执行分配，调用memset将内存设置为0*/
void *calloc(size_t nmemb, size_t size)
{
    if (nmemb == 0 || size == 0)
        return NULL;
    /*避免由算数溢出引起的程序漏洞*/
    size_t cnt = nmemb * size;
    p = (void *)malloc(cnt);
    if (p != NULL)
        memset(p, 0, cnt);
    return p;
}

2.77

//A
x = (x << 4) + x;

//B
x = x - (x << 3);

//C
x = (x << 6) - (x << 2);

//D
x = (x << 4) - (x << 7);

2.78

/*Divide by power of 2. Assume 0 <= k < w-1*/
int divide_power2(int x, int k)
{
    int w = sizeof(int) << 3;
    /*如果x < 0, k不变；如果x >= 0, 将k置为0*/
    int k = k & (x >> (w - 1));
    /*如果k不为0，进行偏置*/
    x += (1 << k) - 1;
    x >>= k;
    return x;
}

2.79

int mul3div4(int x)
{
    int k = 4;
    int y = (x << 2) - x;
    int w = sizeof(int) << 3;
    /*如果y < 0, k不变；如果y >= 0, 将k置为0*/
    k = k & (y >> (w - 1));
    /*如果k不为0，y加上偏置量; 反之，y不变*/
    y += (1 << k) - 1;
    y >>= k;
    return y;
}

2.80

/*no overflow means divide 4 first, then multiple 3*/
int threefourths(int x)
{
    int later = x & 0x3;
    int former = x & ~0x3;
    int w = sizeof(int) << 3;
    int bias = (x >> (w - 1)) & ((1 << 2) - 1);
    former >>= 2;
    former = (former << 1) + former;
    later = (later << 1) + later;
    later = (later + bias) >> 2;
    return later + former;
}

2.81

A：
x = (-1) << k;
B:
x = ((-1) << j) - ((-1) << (k + j));

2.82

/*这种题一般都是考虑0，INT_MIN, INT_MAX*/
//A 
(x < y) == (-x > -y)  false
if x = INT_MIN, y = 0;

//B
((x + y) << 4) + y - x == 17 * y + 15 * x  true

//C 
~x + ~y + 1 == ~(x + y)  true

//D
(ux - uy) == -(unsigned)(y - x)  true  

//E
((x >> 2) << 2) <= x   true

2.83

//A
set x equals the value of 0.yyyyy...
then x * (2 ^ k) = Y + x;
so x = Y / (2 ^ k - 1);

//B
(a)5/7
(b)6/15 = 2/5
(c)19/63

2.84

int float_le(float x, float y)
{
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);
    /*Get the sign bits*/
    unsigned sx = ux >> 31;
    unsigned sy = uy >> 31;
    
    /*Give an expression using only ux, uy, sx, and sy*/
    return (ux << 1) == (uy << 1) ||        //+0与-0相等
           (!sx && sy) ||                    //x为负数，y为正数
           (sx && sy && (ux <= uy)) ||      //都为正数
           (!sx && !sy && (ux >= uy));      //都为负数
}

2.85

//A 
7.0 = V =  111.0(2进制)
s = 0; f = 0.11; M = 1 + f = 1.11; E = 2; e = E + bias = 2 + 2 ^ (k - 1) - 1 = 2 ^ (k - 1) + 1;
位表示(s~e~f) = 0~10...01~1100...000

//B
s = 0;
e_MAX = 11...1110 = 2 ^ k - 2; E_MAX = e_MAX - bias = 2 ^ k - 2 - (2 ^ (k - 1) - 1) = 2 ^ (k - 1) - 1;
一般来说, k < n； 所以当f = 0.111...; M = 1.111...(后面的1的个数为k位); V = 2 ^ (k + 1) - 1;
位表示(s~e~f) = 0~111...111~111...(k个1)00..00

//C
最小的正规格化数:
s = 0; e = 1; E = 2 - 2 ^ (k - 1); f = 0.000...; M = 1.000...; V = 2 ^ E;
它的倒数:
V1 = 2 ^ (-E); -E = 2 ^ (k - 1) - 2; e = 2 ^ k - 3; f = 0.000...;  M = 1.000...;
位表示(s~e~f) = 0~111...1101~000.000

2.86

Description	Value	Decimal
Smallest positive denormalized	0 000…(15)…(62)1	2^(1-Bias-63)
Smallest positive normalized	0 000(14)1 000…(63)	2^(1-Bias)
Largest normalized	0 111…(14)0 111…(63)	2^Bias * (2 - 2^(-63))

2.87

Description	Hex	M	E	V	D
-0	8000	0	-14	-0	-0.0
Smallest value > 2	4001	1025/1024	1	1025/512	2.001953125
512	6000	1	9	512	512.0
Largest denormalized	03FF	1023/1024	-14	1023/(2^24)	1023/(2^24)
-∞	FC00	-	-	-∞	-∞
Number with hex representation 3BB0	3BB0	123/64	-1	123/128	0.9609375

2.88

Format A                                              Format B
---------------------------------------------------------------------------------                                 
Bits               Value                              Bits                 Value
01111 001        -9/8                               1 0111 0010          -9/8
10110 011        176.0                              0 1110 0110          176.0
00111 010        -5/1024                            1 0001 0011          -3/1024
00000 111        7/131072                           0 0000 0001          1/1024
11100 000        -8192.0                            1 1111 1111          -496.0
10111 100        384.0                              0 1111 1000          384.0

2.89

//A
(float) x == (float) dx   true

//B
dx - dy == (double) (x - y)   false
when y = INT_MIN

//C
(dx + dy) + dz == dx + (dy + dz)   true

//D
(dx * dy) * dz == dx * (dy * dz)  false
OVERFLOW!!!   when (dx * dy) overflows but (dy * dz) does not overflow.

//E    
dx / dx == dz / dz     false
when one of x and z is zero

2.90

float fpwr2(int x)
{
    /*Result exponent and fraction*/
    unsigned exp, frac;
    unsigned u;
    /*x is smallest positive denormalized number*/
    if (x < -149)
    {
        /*Too samll. Return 0.0*/
        exp = 0;
        frac = 0;
    }
    /*x is smallest positive normalized number*/
    else if (x < -126)
    {
        /*Denormalized result*/
        exp = 0;
        frac = (1 << (149 + x));
    }
    /*x is special value*/
    else if (x < 128)
    {
        /*Normalized result*/
        exp = x + 127;
        frac = 0;
    }
    else
    {
        /*Too big. Return +∞*/
        exp = 255;
        frac = 0;
    }

    /*Pack exp and frac into 32 bits*/
    u = exp << 23 | frac;
    /*Return as float*/
    return u2f(u);
}

2.91

//A
10000000 10010010000111111011011

//B
11.001001...001

//C
9th

2.92

/*Compute -f. If f is NaN, then return f.*/
float_bits float_negate(float_bits f)
{
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;
    if ((exp == 0xFF && frac == 0) || (exp != 0xFF))
        sign = sign ^ 0x1;
    return (sign << 31) | (exp << 23) | frac;
}

2.93

/*Compute |f|. If f is NaN, then return f.*/
float_bits float_absval(float_bits f)
{
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;
    if (exp == 0xFF && frac != 0)
        return f;
    return (0 << 31) | (exp << 23) | frac;
}

2.94

/*Compute 2*f. If f is NaN, then return f.*/
float_bits float_twice(float_bits f)
{
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;
    if (exp == 0xFF)
        return f;
    if (exp == 0)
        frac <<= 1;
    /*特殊值，此时乘以2要特别注意*/
    else if (exp == 0xFE)
    {
        exp = 0xFF;
        frac = 0;
    }
    else
        exp += 1;
    return (sign << 31) | (exp << 23) | frac;
}

2.95

/*Compute 0.5*f. If f is NaN, then return f.*/
float_bits float_half(float_bits f)
{
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;
    if (exp == 0xFF)
        return f;
    /*round to even
--> 0 just >> 1
--> 0 (round to even) just >> 1
--> 1 just >> 1
--> 1 + 1(round to even) just >> 1 and plus 1*/
    unsigned flag = ((f & 0x3) == 0x3);
    if (exp == 0)
    {
        /*Denormalized*/
        frac = frac >> 1;
        frac += flag;
    }
    else if (exp == 1)
    {
        /*From normalized to denormalized*/
        exp = 0;
        frac = frac >> 1;
        frac += flag;
        frac |= 0x400000;
    }
    else
        /*normalized*/
        exp--;
    return (sign << 31) | (exp << 23) | frac;
}

2.96

/*Compute (int)f. If conversion overflow or f is NaN, return 0x80000000*/
int float_f2i(float_bits f)
{
    /*The biggest float number is 0 11111110 11111111111111111111111*/
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;
    unsigned Bias = 0x7F;
    unsigned num, E, M;
    if (exp < Bias)
    {
        /*less than 1*/
        num = 0;
    }
    else if (exp >= 31 + Bias)
    {
        /*overflow*/
        num = 0x80000000;
    }
    else
    {
        E = exp - Bias;
        M = frac | 0x800000;
        if (E > 23)
            num = M << (E - 23);
        else
            num = M >> (23 - E);
    }
    return sign ? -num : num;
}

2.97

It is so hard!!!