这次更新几题，参考了如下资料：

https://github.com/mofaph/csapp/tree/master/exercise

Chapter 2

66

参考了如下资料：

https://github.com/mofaph/csapp/blob/master/exercise/ex2-66.c

重点是如下操作：

x = x | (x >> 1)

这个操作可以逐步将x化成[0…011…1]的形式，代码如下：

/*
 * Generate mask indicating' leftmost 1 in x. Assume w=32.
 * For example OxFFOO -> 0x8000, and 0x6600 --> 0x4000.
 * If x = 0, then return 0.
 */
#include <stdio.h>

int leftmost_one(unsigned x){
    //第i次增加2^(i-1)个1,化成0...01...1
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    //化成0...010...0
    x = (x + 1) >> 1;

    return x;
}

int find_left_most(unsigned x){
    if (x == 0){
        return 0;
    }
    int d = 0;
    while (x != 0){
        d++;
        x = x >> 1;
    }
    int res = 1 << (d - 1);

    return res;
}

void test(){
    int start = 0;
    int end = 1000;
    for (unsigned i = start; i <= end; i++){
        int d1 = find_left_most(i);
        int d2 = leftmost_one(i);
        if (d1 != d2){
            printf("Wrong answer for %d!\n", i);
            break;
        }
    }
}

int main(){
    printf("%d\n", sizeof(int));
    test();

    return 0;
}

67

主要是如下原因：

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

解决方法是使用了如下性质：

所以得到了如下代码：

#include <stdio.h>

/* The following code does not run properly on some machines */
int bad_int_size_is_32() {
    /* Set most significant bit (msb) of 32-bit machine */
    int set_msb = 1 << 31;
    /* Shift past msb of 32-bit word */
    int beyond_msb = 1 << 32;

    /* set_msb is nonzero when word size >= 32
       beyond_msb is zero when word size <= 32 */
    return set_msb && !beyond_msb;
}

int int_size_is_32() {
    int x = 0x8000000;

    return !(!x);
}

int int_size_is_64() {
    int x = 0x80000000000000;

    return !(!x);
}

void test(){
    int d1 = int_size_is_32();
    int d2 = int_size_is_64();
    int d = sizeof(int);
    if (d1 && (d == 4)){
        printf("int size if 32\n");
    }else if (d2 && (d == 64)) {
        printf("int size if 8\n");
    }else{
        printf("wrong answer\n");
    }
}

int main(){
    test();

    return 0;
}

68

比较常规，主要是要对$n=w$的情形进行特殊处理：

/*
 * Make with least signficant n bits set to 1
 * Examples: n=6 --> 0x3f, n=17 --> 0x1FFFF
 * Assume 1 <= n <= w
 */
#include <stdio.h>

int lower_bits(int x, int n){
    int w = sizeof(int) << 3;
    //判断n是否等于w,相等时为1,否则为0
    int m1 = !(w ^ n);
    //n等于w时为1111,否则为0000
    m1 = ~m1 + 1;
    //n=w时的mask
    int m2 = (~0);
    //其余情形mask
    int m3 = (1 << n) - 1;

    //生成结果
    int r1 = (x | m2);
    int r2 = (x | m3);
    int r = (r1 & m1) | (r2 & (~m1));

    return r;
}

int test_helper(int x, int y, int n){
    if (n == 32){
        return y == -1;
    }

    int flag = 1;
    unsigned x1 = x;
    unsigned y1 = y;
    //检查末n位
    for (int i = 0; i < n; i++){
        int d = y % 2;
        x = x >> 1;
        y = y >> 1;
        if (d == 0){
            flag = 0;
            break;
        }
    }
    //判断剩余部分是否相等
    if (x != y){
        flag = 0;
    };
    
    return flag;
}

void test(){
    int start = -10000;
    int end = 10000;
    int N = sizeof(int) * 8;
    int f = 1;
    for (int n = 0; n <= N; n++){
        if (!f){
            break;
        }
        for (int i = start; i <= end; i++){
            int j = lower_bits(i, n);
            int flag = test_helper(i, j, n);
            if (!flag){
                printf("Wrong answer for i = %d, n = %d\n", i, n);
                printf("i = %x\n", i);
                printf("j = %x\n", j);
                f = 0;
                break;
            }
        }
    }
    if (f){
        printf("Pass test!\n");
    }
}

int main(){
    test();

    return 0;
}

69

/*
 * Do rotating left shift.Assume 0 <=n <w
 * Examples when x = Ox12345678 and w = 32:
 *   n=4 -> Ox23456781， n=20 -> Ox67812345
 */
#include <stdio.h>

unsigned rotateleft(unsigned x, int n){
    int w = sizeof(int) << 3;
    unsigned y = (x << n) | (x >> (w - n));
    return y;
}

void get_bit(unsigned x, int* arr){
    int w = sizeof(int) << 3;
    for (int i = 1; i <= w; i++){
        arr[w - i] = x % 2;
        x = x >> 1;
    }
}

int test_helper(int x, int y, int n){
    int w = sizeof(int) << 3;
    int x1[w];
    int y1[w];
    get_bit(x, x1);
    get_bit(y, y1);

    //比较
    for (int i = w - 1; i >= 0; i--){
        int j = (i - n + w) % w;
        if (x1[i] != y1[j]){
            return 0;
        }
    }
    return 1;
}

void test(){
    int start = 0;
    int end = 10000;
    int N = sizeof(int) * 8;
    int f = 1;
    for (int n = 0; n < N; n++){
        if (!f){
            break;
        }
        for (unsigned i = start; i <= end; i++){
            unsigned j = rotateleft(i, n);
            if (!test_helper(i, j, n)){
                printf("Wrong answer for i = %d, n = %d\n", i, n);
                f = 0;
                break;
            }
        }
    }
    if (f){
        printf("Pass test!\n");
    }
}

int main(){
    test();
    return 0;
}

70

求出n位的表示范围，然后判断x是否属于即可：

/*
 * Return 1 when x can be represented as an n-bit，2's-complement
 * number; 0 otherwise
 * Assume 1 <= n <= w
 */
#include <stdio.h>

int fits_bits(int x, int n){
    int w = sizeof(int) << 3;
    //n=w时为1,否则为0
    int f = !(n ^ w);
    //上下限
    int min_num = - (1 << (n - 1));
    int max_num = (1 << (n - 1)) - 1;
    //求差
    int x1 = x - min_num;
    int x2 = max_num - x;
    //x1>=0时f1=1,否则为1
    int f1 = !(x1 >> (w - 1));
    //x2>=0时f2=1,否则为1
    int f2 = !(x2 >> (w - 1));

    //生成结果
    int res = f | (f1 && f2);

    return res;
}

int fits_bits_(int x, int n){
    int w = sizeof(int) << 3;
    if (n == 32){
        return 1;
    }
    int min_num = - (1 << (n - 1));
    int max_num = (1 << (n - 1)) - 1;
    if (x >= min_num && x <= max_num){
        return 1;
    }

    return 0;
}

void test(){
    int start = -10000;
    int end = 10000;
    int N = sizeof(int) * 8;
    int f = 1;
    for (int n = 1; n <= N; n++){
        if (!f){
            break;
        }
        for (int i = start; i <= end; i++){
            if (fits_bits(i, n) != fits_bits_(i, n)){
                printf("Wrong answer for i = %d, n = %d\n", i, n);
                f = 0;
                break;
            }
        }
    }
    if (f){
        printf("Pass test!\n");
    }
}

int main(){
    test();

    return 0;
}

71

该函数的作用是返回word的第bytenum字节的元素，注意该元素可能为负。

现在看原始代码:

int xbyte(packed_t word, int bytenum){
    return (word >> (bytenum << 3) & 0xFF;
}

该代码不会处理元素为负的情形，正确代码如下（利用了算数右移的性质）：

int xbyte(packed_t word, int bytenum){
    int d = 24 - (bytenum << 3);
    int res = (word << d) >> 24;
}

参考资料：

https://github.com/mofaph/csapp/blob/master/exercise/ex2-71.c

总结

66题比较难，71的技巧比较有意思，可以多回顾几遍。

技巧1
x = x | (x >> 1)

这个操作可以逐步将x化成[0…011…1]的形式。