要求不得使用条件语句、循环语句、分支语句、乘除法、取模运算、相对比较运算（\(<,>,\le,\ge\)）。
2.58
int is_little_endian()
{
unsigned int x = 1;
unsigned char *start = (unsigned char *)(&x);
return start[0];
}
2.59
(y >> 8 << 8) | (x & 0xFF)
2.60
unsigned replace_byte(unsigned x, int i, unsigned char b)
{
int k = i * 8;
return x ^ ((x >> k & 0xFF) << k) ^ (b << k);
}
2.61
A. !(~x)
B. !x
C. !(0xFF ^ (x & 0xFF))
D. !(0xFF ^ (x >> (w - 8) & 0xFF))
2.62
int shifts_are_arithmetic()
{
int w = (sizeof(int)) << 3;
int x = (-1) >> 1;
return x >> (w - 1) & 1;
}
2.63
unsigned srl(signed x, int k)
{
unsigned xsra = (int) x >> k;
int w = (sizeof(int)) << 3;
unsigned v = ~(-1 << (w - k));
return xsra & v; // 只保留 xsra 的最低的 w - k 位即可。
}
int sra(int x, int k)
{
int xsrl = (unsigned) x >> k;
int w = (sizeof(int)) << 3;
int sgn = (1 << (w - 1)) & x;
int v = -1 << (w - k);
v &= !sgn - 1; // 如果 x 为负，则 v 不变，如果 x 非负，则 v 变为 0。
return xsrl | v;
}
2.64
int any_odd_one(unsigned x)
{
unsigned v = 0x555555555;
return !(!(x & v));
}
2.65
int odd_ones(unsigned x)
{
x ^= x >> 1;
x ^= x >> 2;
x ^= x >> 4;
x ^= x >> 8;
x ^= x >> 16; // 此时得到的 x 的最低位是原来的 x 各个位置上的数字异或和的结果
return x & 1;
}
2.66
int leftmost_one(unsigned x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16; // 此时得到的 x 形如 000...000111...111 且最高位 1 的位置和原来相同
return x - (x >> 1);
}
2.67
A. 当左移位数大于等于机器字长时，此时进行的左移操作属于未定义行为，可能返回预期之外的结果。
B. 可以改为
int int_size_is_32() // works for w >= 32
{
int t = 1 << 31;
return t == -t;
}
C. 可以改为
int int_size_is_32() // works for w >= 16
{
int t = 1 << 15;
t <<= 15;
t <<= 1;
return t == -t;
}
2.68
int lower_one_mask(int n)
{
unsigned x = (unsigned)(-1);
int w = (sizeof(int)) << 3;
return (int)(x >> (w - n)); // 这里要用逻辑右移
}
2.69
unsigned rotate_left(unsigned x, int n)
{
int w = (sizeof(int)) << 3;
return (x << n) | (x >> (w - n));
}
2.70
int fits_bits(int x, int n)
{
// 判断 x 的前 w-n 位是否全为 0 或者全为 1 即可
unsigned int v = (~0u) >> (w - n);
int a = x & ((int)(v));
v = ~v;
int b = x | ((int)(v));
return x == a || x == b;
}
2.71
A. 这段代码将抽取出的字节作为一个无符号数返回，而不是有符号数。
B. 正确的实现：
int xbyte(packed_t word, int bytenum)
{
int x = (word >> (bytenum << 3)) & 0xFF;
x -= (x >> 7 & 1) << 8;
return x;
}
2.72
A. 因为 sizeof(val) 返回的是无符号数类型，计算 maxbytes-sizeof(val) 前会进行强制转换，进行的是无符号数减法，结果总是大于等于 0 的。
B. 将条件改为 if(maxbytes >= sizeof(val)) 即可。
2.73
int saturating_add(int x, int y)
{
int w = (sizeof(int)) << 3;
int TMin = 1 << (w - 1);
int TMax = TMin - 1;
int sum = x + y;
int pos_overflow = !(x & TMin) && !(y & TMin) && (sum & TMin); // 用逻辑运算代替 if 语句
int neg_overflow = (x & TMin) && (y & Tmin) && !(sum & TMin);
pos_overflow && (sum = TMax); // 用短路特性代替 if 语句
neg_overflow && (sum = TMin);
return sum;
}
2.74
int sub_ok(int x, int y)
{
int sub = x - y;
int w = (sizeof(int)) << 3;
int TMin = 1 << (w - 1);
int pos_overflow = !(x & TMin) && (y & TMin) && (sub & TMin);
int neg_overflow = (x & TMin) && !(y & TMin) && !(sub & TMin);
return !(pos_overflow) && !(neg_overflow);
}
2.75
unsigned unsigned_high_prod(unsigned x, unsigned y)
{
int w = (sizeof(int)) << 3;
int v = signed_high_prod((int)(x), (int)(y));
unsigned result = (unsigned)(v);
result += (!(x >> (w - 1) & 1) - 1) & y;
result += (!(y >> (w - 1) & 1) - 1) & x;
return result;
}
2.76
void *calloc(size_t nmemb, size_t size) // 这里必然会用到乘法
{
if (!nmemb || !size)
return NULL;
size_t bufsiz = nmemb * size;
if (bufsiz / size == nmemb)
{
void *ptr = malloc(bufsiz);
if (ptr != NULL)
memset(ptr, 0, bufsiz);
return ptr;
}
return NULL;
}
2.77
A. (x << 4) + x
B. x - (x << 3)
C. (x << 6) - (x << 2)
D. (x << 4) - (x << 7)
2.78
int divide_power2(int x, int k)
{
int w = (sizeof(int)) << 3;
int bias = (1 << k) - 1;
int sgn = x >> (w - 1) & 1;
bias &= (!sgn) - 1;
return (w + bias) >> k;
}
2.79
int mul3div4(int x)
{
x = (x << 1) + x;
int bias = 3;
int w = (sizeof(int)) << 3;
bias &= !(x >> (w - 1) & 1) - 1;
return (x + bias) >> 2;
}
2.80
题目的意思应该是计算 \(\frac 3 4 x\) 的值并向零舍入。
int threefourths(int x) // 分成前 30 位和后 2 位分别计算
{
int w = (sizeof(int)) << 3;
int a = x ^ (x & 3);
int b = x & 3;
int result = a >> 2;
result += result << 1; // 前 30 位不存在舍入问题，先除再乘
b += b << 1;
b += (!(x >> (w - 1) & 1) - 1) & 3;
b >>= 2; // 后 2 位不存在溢出问题，先乘再除
result += b;
return result;
}
2.81
A. (-1) << k
B. (unsigned)((-1) << (k + j)) >> k
2.82
A. 当 x 和 y 其中恰好有一者为 TMin 时，表达式为 0。
B. 总为 1，因为带符号的加减法与乘法满足交换律与结合律。
C. 总为 1，因为反码 = 补码 + 1。
D. 总为 1，因为类型转换时二进制编码不变。
E. 总为 1，因为算术右移是向下取整的。
2.83
A. 记这个无穷串的值为 \(x\) ，则 \(x\times 2^k-Y=x\) ，解得 \(x=\frac{Y}{2^k-1}\) 。
B. \((a).\frac{5}{7}\ (b).\frac{6}{15}=\frac{2}{5}\ (c).\frac{19}{63}\)