版权声明：本文为 gfson 原创文章，转载请注明出处。
注：作者水平有限，文中如有不恰当之处，请予以指正，万分感谢。
2.55 - 2.57
2.55 - 2.57.png
- 答案：
#include <stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len){
size_t i;
for(i=0;i<len;i++)
printf(" %.2x",start[i]);
printf("\n");
}
void show_short(short x){
show_bytes((byte_pointer) &x, sizeof(short));
}
void show_int(int x){
show_bytes((byte_pointer) &x, sizeof(int));
}
void show_long(long x){
show_bytes((byte_pointer) &x, sizeof(long));
}
void show_float(float x){
show_bytes((byte_pointer) &x, sizeof(float));
}
void show_double(double x){
show_bytes((byte_pointer) &x, sizeof(double));
}
int main(void){
short s = 34;
int i = 34;
long l = 34L;
float f = 34.0f;
double d = 34.0;
show_short(s);
show_int(i);
show_long(l);
show_float(f);
show_double(d);
return 1;
}
上述代码运行后，结果如下：
result.png
对运行结果进行分析：
- 可以直观的看到当前计算机上各个类型所占的字节。其中，short 占 2 个字节， int、long、float 占 4 个字节，double 占 8 个字节。
- 可以看出当前机器字节顺序使用的是小端法。
- short、int、long 计算：2 * 16 + 2 = 34。
- float 计算：
- 0x420800 = [0100 0010 0000 1000 0000 0000]2
- 由于遵循 IEEE 标准，float 中 s 字段为 1，k = 8，n = 23，所以：
- Bias = 2k-1 - 1 = 127，
e = [1000 0100] 2 = 132，
E = e - Bias = 5，
f = [0.000 1000 0000 0000 0000 0000]2 = 1/16，
M = 1 + f = 1 + 1/16，
s = 0，
V = （-1）s * 2E * M = 32 * （1 + 1/16） = 34。
- Bias = 2k-1 - 1 = 127，
- double 计算：
- 0x4041000000000000 = [0100 0000 0100 0001 0000 0000 ... 0000]2
- 由于遵循 IEEE 标准，double中 s 字段为 1，k = 11，n = 52，所以：
- Bias = 2k-1 - 1 = 210 - 1，
e = [100 0000 0100] 2 = 210 + 4，
E = e - Bias = 5，
f = [0.000 1000 0000 0000 0000 0000 ... 0000]2 = 1/16，
M = 1 + f = 1 + 1/16，
s = 0，
V = （-1）s * 2E * M = 32 * （1 + 1/16） = 34。
- Bias = 2k-1 - 1 = 210 - 1，
2.58
2.58.png
- 答案：
int is_little_endian(){
int a = 1;
return *((char*)&a);
}
int main(void){
int result = is_little_endian();
printf("result is: %d \n",result);
return 1;
}
2.59
2.59.png
- 答案：
int mix(int x, int y){
return (x & 0xFF) | (y & (~0xFF));
}
int main(void){
int result = mix(0x89AECDEA,0x76743210);
printf("result is: %x \n",result);
return 1;
}
2.60
2.60.png
- 答案（两种方法）：
unsigned replace_byte_1(unsigned x, int i, unsigned char y){
char* start = (char*)&x;
start[i] = y;
return x;
}
unsigned replace_byte_2(unsigned x, int i, unsigned char y){
return (x & ~(0xFF<<(i<<3)) | (y << (i<<3)));
}
int main(void){
unsigned result_1 = replace_byte_1(0x12345678, 2, 0xAB);
printf("result_1 is: %x \n",result_1);
unsigned result_2 = replace_byte_2(0x12345678, 3, 0xAB);
printf("result_2 is: %x \n",result_2);
return 1;
}
对 replace_byte_2 的解释：
- 以参数（0x12345678, 2, 0xAB）为例，从 0x12345678 -> 0x12AB5678 需要经历如下过程：
- 0xAB -> 0x00AB0000，0xAB << 2 * 2 *4，0xAB << 2 << 3，y << (i << 3)
- 0x12345678 -> 0x12005678，0x12345678 & 0xFF00FFFFFF，0x12345678 & ~0x00FF000000，0x12345678 & ~(0xFF << 2 * 2 * 4)，0x12345678 & ~(0xFF << 2 << 3)，(x & ~ (0xFF << (i<<3))
- 0x12AB5678 = 0x00AB0000 | 0x12005678 = (x & ~(0xFF << (i<<3)) | (y << (i<<3)))
位级整数编码规则
位级整数编码规则-1.png
位级整数编码规则-2.png
接下来的作业需要遵循位级整数编码规则
2.61
2.61.png
- 答案：
- A: !(~x)
- B: !x
- C: !((~x) & 0xFF)
- D: !(x & (~0xFF)) 或者 !(x>>((sizeof(int)-1)<<3))
经验
- 核心判断是零与非零，目的是需要达到在一种情况下结果所有位为 0，其他情况下有些位不为 0。
- 在 D 中，可以通过 x & (~0xFF) 的方法使得除最高位字节以外的字节都为 0，也可以通过 (x>>((sizeof(int)-1)<<3)) 的方法将最高位右移至最低位，来判断结果所有位是否为 0。
2.62
2.62.png
- 答案（两种方法）：
int int_shifts_are_arithmetic_1(){
return !(((0xFF<<((sizeof(int)-1)<<3))>>((sizeof(int)-1)<<3)) + 0x01 );
}
int int_shifts_are_arithmetic_2(){
int x = -1;
return (x>>1) == -1;
}
int main(void){
int result_1 = int_shifts_are_arithmetic_1();
printf("result_1 is: %d \n",result_1);
int result_2 = int_shifts_are_arithmetic_2();
printf("result_2 is: %d \n",result_2);
return 1;
}
经验
- 第一种方法，0xFF 先左移到最高字节，然后右移到最低字节，判断其所有位是否为 1。
- 第二种方法，非常巧妙，通过 -1 既 0xFFFFFFFF 右移一位判断其值是否改变。
2.63
2.63.png
- 答案：
unsigned srl(unsigned x, int k){
unsigned xsra = (int) x >> k;
int w = sizeof(int)*8;
unsigned z = 2 << (w-k-1);
return (z - 1) & xsra;
}
int sra(int x, int k){
int xsrl = (unsigned) x >> k;
int w = sizeof(int) << 3;
unsigned z = 1 << (w-k-1);
unsigned mask = z - 1;
unsigned right = mask & xsrl;
unsigned left = ~mask & (~(z&xsrl) + z);
return left | right;
}
int main(void){
unsigned result_srl = srl(-1,1);
printf("result_srl is: %x \n",result_srl);
int result_sra = sra(-1,1);
printf("result_sra is: %x \n",result_sra);
return 1;
}
运行结果如下：
Result.png
解析
- 对于 srl，目的就是将前面的高位清 0，即 xsra & (1<<(w-k) - 1)。额外注意 k==0 时，不能使用 1<<(w-k)，于是改用 2<<(w-k-1)。
- 注意，最大移位数不能够
> w-1，因为移位数达到 w 之后的行为是未定义的，没有标准。 - 对于形如 0x00001111 的情况，均可以使用
0x00010000 -1的方式获得。
- 对于 sra，目的是将 xrsl 的第 w-k-1 位扩展到前面的高位。这个可以利用取反加 1 来实现，不过这里的加 1
是加1<<(w-k-1)。如果 x 的第 w-k-1 位为 0，取反加 1 后，前面位全为 0，如果为 1，取反加 1 后就全是 1。最后再使用相应的掩码得到结果。
- 本题将第 w-k-1 位扩展到前面高位的思想非常巧妙，需要根据代码答案仔细体会。
2.64
2.64.png
- 答案：
int any_odd_one(unsigned x){
return !!(x & 0x55555555);
}
int main(void){
int result = any_odd_one(0xaaaaaaaa);
printf("result is: %d \n", result);
return 1;
}
解析
- 此题思路是将偶数位全部取 0，奇数位不变。
- 需要注意的一点时，最后结果是 bool 类型，如果直接
x & 0x55555555得出的不是 bool 类型，所以需要使用 ! 进行转换，既!!(x & 0x55555555)。
2.65
2.65.png
- 答案：
int odd_ones(unsigned x){
x = x ^ (x >> 1);
x = x ^ (x >> 2);
x = x ^ (x >> 4);
x = x ^ (x >> 8);
x = x ^ (x >> 16);
return x & 1;
}
int main(void){
int result = odd_ones(9);
printf("result is: %d \n", result);
return 1;
}
解析
- 由 1^1 = 0，1^0 = 1，0^0 = 0，可知，偶数个 1 异或的结果是 0，奇数个 1 异或的结果是 1。
- 比如，求
10101110中的 1 的个数是奇数还是偶数，由1^0^1^0^1^1^1^0 = 1可知，个数为奇数。 - 所以我们得出结论，x 的每个位异或，最后的结果为 0，则有偶数个 1，为 1，则有奇数个 1。
- 回到本题，我们的目的是为了将 x 中的所有位的值进行异或运算，使用分治的思想：
-
x ^ (x >> 1)表示 x 中的每一位和其后一位进行异或，假设得到的结果为 x1，则 x1 中的第 1 位的值表示 x 中第 1、2 位的异或结果，x1 中的第 3 位的值表示 x 中第 3、4 位的异或结果。 - 这个时候，
x ^ (x >> 2)既 x1 ^ (x1 >> 2)，表示 x1 中的每一位和其后第二位进行异或，假设得到的结果为 x2，则** x2 中的第 1 位的值表示 x1 中第 1、3 位的异或结果，既表示 x 中第 1、2、3、4 位的异或结果**，x2 中的第 5 位的值表示 x1 中第 5、7 位的异或结果，既表示 x 中第 5、6、7、8 位的异或结果。 - 根据以上可以推出，
x ^ (x >> 4)的结果 x3 的第一位表示 x2 的 1、5 位的异或结果，表示 x 的 1、2、3、4、5、6、7、8 位的异或结果。 - 同理，
x ^ (x >> 8)的结果 x4 的第一位表示 x 的 1 到 16 位的异或结果，x ^ (x >> 16)的结果 x5 的第一位表示 x 的 1 到 32 位的异或结果。 - 所以，最后只有通过 x5 & 1 来判断 x5 的第一位是 0 还是 1 即可。
2.66
2.66.png
- 答案：
int leftmost_one(unsigned x){
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return x^(x>>1);
}
int main(void){
int result = leftmost_one(0x9f);
printf("result is: %x \n", result);
return 1;
}
解析
- 根据提示，我们可以想到
00001111 ^ 00000111 = 00001000，所以接下来需要将 x 转化为 [00…011…1] 的形式。 - 我们可以想到，用最高位的 1 分别与其他位进行或运算。
- 假设 x 就是 10000000... 该如何让每一位都为 1。方法如下：
- 先是 x 右移1位再和原 x 进行或，变成 1100000...，再让结果右移 2 位和原结果或，变成 11110000...，最后到 16 位，变成 11111111...。
2.67
2.67.png
- 答案：
A：1<<32 在 32 位机器上是未定义的。
B：将1<<32修改为2<<31。
C：代码如下：
int bad_int_size_is_32(){
int a = 1<<15;
a<<=15;
int set_msb = a<<1;
int beyond_msb = a<<2;
return set_msb && !beyond_msb;
}
int main(void){
int result = bad_int_size_is_32();
printf("result is: %d \n", result);
return 1;
}
解析
- C 中需要将 31 拆分为
15+15+1。
2.68
2.68.png
- 答案：
int lower_one_mask(int n){
return (2 << (n-1)) - 1;
}
int main(void){
int result = lower_one_mask(32);
printf("result is: %x \n", result);
return 1;
}
2.69
2.69.png
- 答案：
unsigned rotate_left(unsigned x, int n){
return (x << n)|(x >> 1 >> ((sizeof(int)*8)- n -1));
}
int main(void){
unsigned result = rotate_left(0x12345678, 32);
printf("result is: %x \n", result);
return 1;
}
2.70
2.70.png
- 答案：
int fits_bits(int x, int n){
x >>= (n-1);
return !x || !(~x);
}
int main(void){
int result = fits_bits(8, 4);
printf("result is: %d \n", result);
return 1;
}
解析
- 这一题是看 x 的值是否在 - 2^(n-1) 到 2^(n-1) - 1 之间。
- 如果 x 满足这个条件，则其第 n-1 位就是符号位。如果该位为 0，则前面的 w-n 位均为 0，如果该位为 1，则前面的 w-n 位均为1。所以本质是判断，x 的高 w-n+1 位是否为 0 或者为 -1。
2.71
2.71.png
- 答案：
A：得到的结果是 unsigned，而并非扩展为 signed 的结果。
B：正确代码如下：
int xbyte(packed_t word, int bytenum){
int ret = word << ((3 - bytenum)<<3);
return ret >> 24;
}
解析
- B 中使用 int，将待抽取字节左移到最高字节，再右移到最低字节即可。
2.72
2.72.png
- 答案
A：size_t 是无符号整数，因此左边都会先转换为无符号整数，它肯定是大于等于 0 的。
B：判断条件改为if(maxbytes > 0 && maxbytes >= sizeof(val))。
解析
- B 中为什么要先判断
maxbytes > 0，是因为如果maxbytes < 0，在执行maxbytes >= sizeof(val))时，会先将 maxbytes 转化为无符号数，这样就会导致结果与预期的不符合。
2.73
2.73.png
- 答案
#include <limits.h>
int saturating_add(int x, int y){
int w = sizeof(int)<<3;
int t = x + y;
int ans = x + y;
x>>=(w-1);
y>>=(w-1);
t>>=(w-1);
int pos_ovf = ~x&~y&t;
int neg_ovf = x&y&~t;
int novf = ~(pos_ovf|neg_ovf);
return (pos_ovf & INT_MAX) | (novf & ans) | (neg_ovf & INT_MIN);
}
int main(void){
int result = saturating_add(INT_MIN, -1);
printf("result is: %x \n", result);
return 1;
}
解析
- 对于有符号整数相加，溢出的规则可以总结为：
- t = a+b。
- 如果 a，b 异号，则肯定不会溢出。
- 如果 a，b 中有一个为 0，则肯定不会溢出。
- 如果
a>0 && b>0，则只有当 t<0 时才算正溢出。 - 如果
a<0 && b<0，则只有当 t>0 时才算负溢出。 - 所以：
- a > 0，b > 0，t < 0，正溢出。
- a < 0，b < 0，t > 0，负溢出。
思路
- 碰到一个复杂问题时，如果一下子无法看出规律，应该要善于总结条件和推理结果，从这个过程中寻找规律。
2.74
2.74.png
- 答案
#include <stdint.h>
int tsub_ok(int x, int y){
int w = sizeof(int)<<3;
int t = x - y;
x>>=(w-1);
y>>=(w-1);
t>>=(w-1);
return !((x != y) && (y == t));
}
int main(void){
int result = tsub_ok(INT32_MIN, 1);
printf("result is: %d \n", result);
return 1;
}
解析
- 对于有符号整数相减，溢出的规则可以总结为：
- t = a-b。
- 如果 a，b 同号，则肯定不会溢出。
- 如果 a，b 中有一个为 0，则肯定不会溢出。
- 如果
a>0 && b<0，则只有当 t<0 时才算溢出。 - 如果
a<0 && b>0，则只有当 t>0 时才算溢出。 - 所以，a，b 异号，t，b 同号即可判定为溢出。
2.75
2.75.png
- 答案
unsigned unsigned_high_prod(unsigned x, unsigned y){
int w = sizeof(int)<<3;
return signed_high_prod(x, y) + ((int)x>>(w-1)) & y + ((int)y>>(w-1)) & x;
}
解析
- 假如 x'、y' 分别表示 2 的补码表示的有符号数 x、y 对应的无符号数，xw-1、yw-1 分别表示有符号数 x、y 的最高位符号位，则在数据类型 unsigned 是 w 位的机器上，有如下结论：
- x' = x + xw-1 * 2w
- y' = y + yw-1 * 2w
- x'y' = xy + x * yw-1 * 2w + y * xw-1 * 2w + xw-1 * yw-1 * 22w
- 我们知道，在 w 位机器上，无论是有符号数，还是无符号数，乘法的本质是将结果 2w 位截断为低 w 位，然后再用相应的有符号数或无符号数表示。所以，乘法结果的高 w 位表示需要在乘法结果的基础上右移 w 位，即除以 2w，假设 x'y'_h、xy_h 分别为其乘积的高位表示，则有如下结论：
- x'y'_h = xy_h + x * yw-1 + y * xw-1 + xw-1 * yw-1 * 2w
- 由于 x'y'_h 只有 w 位，所以 xw-1 * yw-1 * 2w 最后会被截断掉，对结果没有影响，则有如下结论：
- x'y'_h = xy_h + x * yw-1 + y * xw-1
- 由于本题要求遵循位级编码规则，即不能使用乘号，所以可以进行如下变换，巧妙的使用 int 进行移位，并进行与运算：
- x * yw-1 = x * (y>>(w-1)) = ((int)y >> (w-1)) & x
- y * xw-1 = y * (x>>(w-1)) = ((int)x >> (w-1)) & y
- 所以最后结果为：
- x'y'_h = xy_h + ((int)y >> (w-1)) & x + ((int)x >> (w-1)) & y
2.76
2.76.png
- 答案
//TODO
2.77
2.77.png
- 答案
A. (x << 4) + x
B. x - (x << 3)
C. (x << 6) - (x << 2)
D. (x << 4) - (x << 7)
2.78
2.78.png
- 答案
int divide_power2(int x, int k){
int ans = x>>k;
int w = sizeof(int)<<3;
ans += (x>>(w-1)) && (x&((1<<k)-1));
return ans;
}
解析
- 首先计算
x>>k。 - 然后考虑除法的向零舍入，即 x<0 且 x 的最后 k 位不为零时要加一。
- 必须保证除法是向零舍入的。
- 当 x>0 时，x>>k 的结果是向下舍入的，由于 x 是正数，所以是向零舍入，符合要求。
- 当 x<0 且 x 的最后 k 位不为零时，x>>k 的结果是向下舍入的，由于 x 是负数，此时向下舍入后的值不符合向零舍入的目的，需要将结果加一才符合向零舍入。
2.79
2.79.png
- 答案
// TODO
