【CS:APP】第二章家庭作业

2017-06-14 本文已影响0人 gfson

版权声明：本文为 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]₂
由于遵循 IEEE 标准，float 中 s 字段为 1，k = 8，n = 23，所以：
- Bias = 2^k-1 - 1 = 127，
  e = [1000 0100] ₂ = 132，
  E = e - Bias = 5，
  f = [0.000 1000 0000 0000 0000 0000]₂ = 1/16，
  M = 1 + f = 1 + 1/16，
  s = 0，
  V = （-1）^s * 2^E * M = 32 * （1 + 1/16） = 34。

double 计算：

0x4041000000000000 = [0100 0000 0100 0001 0000 0000 ... 0000]₂
由于遵循 IEEE 标准，double中 s 字段为 1，k = 11，n = 52，所以：
- Bias = 2^k-1 - 1 = 2¹⁰ - 1，
  e = [100 0000 0100] ₂ = 2¹⁰ + 4，
  E = e - Bias = 5，
  f = [0.000 1000 0000 0000 0000 0000 ... 0000]₂ = 1/16，
  M = 1 + f = 1 + 1/16，
  s = 0，
  V = （-1）^s * 2^E * M = 32 * （1 + 1/16） = 34。

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;
}

以参数（0x12345678, 2, 0xAB）为例，从 0x12345678 -> 0x12AB5678 需要经历如下过程：
1. 0xAB -> 0x00AB0000，0xAB << 2 * 2 *4，0xAB << 2 << 3，y << (i << 3)
2. 0x12345678 -> 0x12005678，0x12345678 & 0xFF00FFFFFF，0x12345678 & ~0x00FF000000，0x12345678 & ~(0xFF << 2 * 2 * 4)，0x12345678 & ~(0xFF << 2 << 3)，(x & ~ (0xFF << (i<<3))
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 中的每一位和其后一位进行异或，假设得到的结果为 x₁，则 x₁ 中的第 1 位的值表示 x 中第 1、2 位的异或结果，x₁ 中的第 3 位的值表示 x 中第 3、4 位的异或结果。
这个时候，x ^ (x >> 2) 既 x₁ ^ (x₁ >> 2)，表示 x₁ 中的每一位和其后第二位进行异或，假设得到的结果为 x₂，则** x₂ 中的第 1 位的值表示 x₁ 中第 1、3 位的异或结果，既表示 x 中第 1、2、3、4 位的异或结果**，x₂ 中的第 5 位的值表示 x₁ 中第 5、7 位的异或结果，既表示 x 中第 5、6、7、8 位的异或结果。
根据以上可以推出，x ^ (x >> 4) 的结果 x₃ 的第一位表示 x₂ 的 1、5 位的异或结果，表示 x 的 1、2、3、4、5、6、7、8 位的异或结果。
同理，x ^ (x >> 8) 的结果 x₄ 的第一位表示 x 的 1 到 16 位的异或结果，x ^ (x >> 16) 的结果 x₅ 的第一位表示 x 的 1 到 32 位的异或结果。
所以，最后只有通过 x₅ & 1 来判断 x₅ 的第一位是 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 对应的无符号数，x_w-1、y_w-1 分别表示有符号数 x、y 的最高位符号位，则在数据类型 unsigned 是 w 位的机器上，有如下结论：
- x' = x + x_w-1 * 2^w
- y' = y + y_w-1 * 2^w
- x'y' = xy + x * y_w-1 * 2^w + y * x_w-1 * 2^w + x_w-1 * y_w-1 * 2^2w
我们知道，在 w 位机器上，无论是有符号数，还是无符号数，乘法的本质是将结果 2w 位截断为低 w 位，然后再用相应的有符号数或无符号数表示。所以，乘法结果的高 w 位表示需要在乘法结果的基础上右移 w 位，即除以 2^w，假设 x'y'_h、xy_h 分别为其乘积的高位表示，则有如下结论：
- x'y'_h = xy_h + x * y_w-1 + y * x_w-1 + x_w-1 * y_w-1 * 2^w
- 由于 x'y'_h 只有 w 位，所以 x_w-1 * y_w-1 * 2^w 最后会被截断掉，对结果没有影响，则有如下结论：
  - x'y'_h = xy_h + x * y_w-1 + y * x_w-1
由于本题要求遵循位级编码规则，即不能使用乘号，所以可以进行如下变换，巧妙的使用 int 进行移位，并进行与运算：
- x * y_w-1 = x * (y>>(w-1)) = ((int)y >> (w-1)) & x
- y * x_w-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

【CS:APP】第二章家庭作业

2.55 - 2.57

2.58

2.59

2.60

位级整数编码规则

2.61

2.62

2.63

2.64

2.65

2.66

2.67

2.68

2.69

2.70

2.71

2.72

2.73

2.74

2.75

2.76

2.77

2.78

2.79

猜你喜欢

热点阅读

【CS:APP】第二章 家庭作业

2.55 - 2.57

2.58

2.59

2.60

位级整数编码规则

2.61

2.62

2.63

2.64

2.65

2.66

2.67

2.68

2.69

2.70

2.71

2.72

2.73

2.74

2.75

2.76

2.77

2.78

2.79

猜你喜欢

热点阅读

【CS:APP】第二章家庭作业