深入理解计算机系统 第2章 习题解析 Part1

之前学习CMU的15-213被劝退后，又通过华盛顿大学的Hardware Software Interface复习了书籍前面一部分的内容。两次学习后感受到《深入理解计算机系统》一书的重要性，所以决定细读该书，定个小目标，刷完该书的80%习题。由于工作后时间比较紧张，所以每周更新个5题左右。

电子书地址：

http://eol.bnuz.edu.cn/meol/common/script/preview/download_preview.jsp?fileid=2169600&resid=242120&lid=28605

Chapter 2

58

只要理解大端小端的定义即可：

考虑一个$w$位的整数，其位表示为$[ x_{w-1},x_{w-2}, \cdots, x_{1}, x_{0}]$，其中$x_{w-1}$是最高有效位，$x_0$是最低有效位。

最低有效字节在最前面的方式，称为小端法(little endian)；最高有效字节在最前面的方式，称为大端法(big endian)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char *byte_pointer;

int is_little_endian(){
    int num = 0x100;
    //小地址靠前
    //小端:00,01
    //大端:01,00
    byte_pointer p = (byte_pointer) &num;
    size_t size = sizeof(int);
    if (p[0]){
        return 0;
    }else{
        return 1;
    }
}

int main(){
    int res = is_little_endian();
    if (res){
        printf("This machine is little endian!\n");
    }else{
        printf("This machine is big endian!\n");
    }

    return 0;
}

59

#include <stdio.h>

int calculate(int x, int y){
    int mask = 0xFF;
    int z = (x & mask) | (y & (~mask));

    return z;
}

int main(){
    int x = 0x89ABCDEF;
    int y = 0x76543210;
    int z = calculate(x, y);
    printf("x:%x\n", x);
    printf("y:%x\n", y);
    printf("z:%x\n", z);

    return 0;
}

60

#include <stdio.h>

unsigned replace_byte (unsigned x, int i, unsigned char b){
    int d = i * 8;
    int mask = (0xFF << d);
    //注意不能使用char类型
    unsigned c = ((unsigned)b) << d;
    unsigned y = (x & (~mask)) | c;

    return y;
}

int main(){
    unsigned x = 0x12345678;
    unsigned y = 0xAB;
    for (int i = 0; i < 4; i++){
        printf("%x\n", replace_byte(x, i, y));
    }
    
    return 0;
}

61

#include <stdio.h>

int expression(int x){
    int w = sizeof(int) << 3;
    //计算结果
    int mask1 = !(x ^ (-1));
    int mask2 = !(x ^ 0);
    int mask3 = !((x & 0xFF) ^ 0xFF);
    int mask4 = !((x & (0xFF << (w - 8))) ^ 0);
    int res = mask1 | mask2 | mask3 | mask4;

    return res;
}

int f(int x){
    int w = sizeof(int) << 3;
    int y = x & 0xFF;
    int z = (x >> (w - 8)) & 0xFF;
    if (x == 0xFFFFFFFF){
        return 1;
    }else if (x == 0){
        return 1;
    }else if (y == 0xFF){
        return 1;
    }else if (z == 0){
        return 1;
    }else{
        return 0;
    }
}

void test(){
    int start = -10000;
    int end = 10000;
    //记录结果
    int flag = 1;

    for (int i = start; i <= end; i++){
        if (expression(i) != f(i)){
            printf("Wrong answer for %x!\n", i);
            flag = 0;
            break;
        }
    }

    if (flag){
        printf("Test sucess!\n");
    }else{
        printf("Test fail!\n");
    }
    
    return;
}

int main(){
    test();

    return 0;
}

62

利用-1的逻辑右移等于-1即可：

#include <stdio.h>

int int_shifts_are_arithmetic(){
    int x = -1;
    int y = x >> 1;
    //判断是否相等
    int res = !(x ^ y);

    return res;
}

int main(){
    int res = int_shifts_are_arithmetic();
    if (res){
        printf("Arithmetic right shift!\n");
    }else{
        printf("Logic right shift!\n");
    }

    return 0;
}

63

srl函数需要将前k个比特设为0，所以需要如下形式的mask：

$$\underbrace{0\ldots 0}_{k个0}1\ldots 1$$

注意k=0时要特殊处理。

sra将前k个比特设为符号位，注意k=0时也要特殊处理。

这里使用如下技巧，给定s(0或1)，如何生成

$$1\ldots 1,0\ldots0$$

方法如下：

//s=0时mask=1111，否则为1110
int mask = ~s;
//s=0时mask=0000，否则为1111
mask = mask + 1;

代码如下：

#include <stdio.h>

unsigned srl(unsigned x, int k){
    /* Perform shift arithmetically */
    unsigned xsra = (int) x >> k;
    //w需要特殊处理
    //int比特数
    int w = sizeof(int) << 3;
    //k=0时mask=0，否则为1
    int mask = !(!k);
    //k=0时mask=1111，否则为1110
    mask = ~mask;
    //k=0时mask=0000，否则为1111
    mask = mask + 1;
    //生成1...10...0
    mask = mask << (w - k);
    //生成0...01...1
    mask = ~mask;
    //生成结果
    xsra = xsra & mask;

    return xsra;
}

int sra(int x, int k){
    /* Perform shift logically */
    unsigned xsrl = (unsigned) x >> k;
    //int比特数
    int w = sizeof(int) << 3;
    //获得符号位
    int s = x & (1 << (w - 1));
    //根据符号位生成mask
    s = !(!s);
    //k=0时s=0
    s = s & (!(!k));
    //取反,x<0时为1110,x>=0时为1111,k=0时为1111
    int mask = ~s;
    //x<0时为1111,x>=0时为0000,k=0时为0000
    mask = mask + 1;
    //移位,生成ssss0000
    mask = mask << (w - k);
    //生成结果
    xsrl = xsrl | mask;

    return xsrl;
}

void test_srl(){
    int w = sizeof(int) << 3;
    int start = -100;
    int end = 100;

    int flag = 1;
    for (int i = start; i <= end; i++){
        if (!flag){
            break;
        }
        for (int k = 0; k < w; k++){
            unsigned res = (unsigned)i >> k;
            unsigned ans = srl(i, k);
            if (ans != res){
                printf("Wrong answer for %d!\n", i);
                flag = 0;
                break;
            }
        }
    }

    if (flag){
        printf("srl test succeed.\n");
    }else{
        printf("srl test fail.");
    }
}

void test_sra(){
    int w = sizeof(int) << 3;
    int start = -1000;
    int end = 1000;

    int flag = 1;
    int f2 = 1;

    for (int i = start; i <= end; i++){
        if (!f2){
            break;
        }
        for (int k = 0; k < w; k++){
            int res = i >> k;
            int ans = sra(i, k);
            if (ans != res){
                printf("Wrong answer for %d!\n", i);
                f2 = 0;
                break;
            }
        }
    }

    if (f2){
        printf("sra test succeed.\n");
    }else{
        printf("sra test fail.");
    }
}

int main(){
    test_srl();
    test_sra();

    return 0;
}

64

#include <stdio.h>

/* Return 1 when any odd bit of x equals 1; 0 otherwise.
   Assume w=32 */
int any_odd_one (unsigned x){
    //A=1010,这里假设最低位索引为0
    int mask = 0xAAAAAAAA;
    int res = x & mask;
    res = !!(res);

    return res;
}

int any_odd_one_(unsigned x){
    int res = 0;
    int i = 0;
    while (x != 0){
        int d = x % 2;
        x /= 2;
        if (i && d){
            res = 1;
            break;
        }
        i = 1 - i;
    }

    return res;
}

void test(){
    int start = -10000;
    int end = 10000;
    int flag = 1;
    for (int i = start; i <= end; i++){
        if (any_odd_one(i) != any_odd_one_(i)){
            flag = 0;
            break;
        }
    }

    if (flag){
        printf("Test pass!\n");
    }else{
        printf("Test fail!\n");
    }
}

int main(){
    test();

    return 0;
}

65

这里利用如下技巧：

假设

$$\begin{aligned} x&=[ x_{2n-1},x_{2n-2}, \cdots, x_{1}, x_{0}]\\ a &=[ x_{2n-1},x_{2n-2}, \cdots, x_{n-2}]\\ b&=[ x_{n-1},x_{n-2}, , \cdots, x_{0}] \end{aligned}$$

记$T(x)$为$x$中$1$的个数的奇偶性，那么很容易验证

$$T(x)=T(a\text{^} b)$$

注意到

$$a\text{^}b = ((x >> n)\text{^} x)\ \&\ 0\text{x}\underbrace {1\ldots 1}_{n个1}$$

所以我们可以得到如下代码

//只考虑16位
int a1 = (x ^ (x >> 16)) & 0xFFFF;
//只考虑8位
int a2 = (a1 ^ (a1 >> 8)) & 0xFF;
//只考虑4位
int a3 = (a2 ^ (a2 >> 4)) & 0xF;
//只考虑2位
int a4 = (a3 ^ (a3 >> 2)) & 0x11;
//生成结果
int res = (a4 ^ (a4 >> 1)) & 1;

这样一共需要15次运算，显然超过了要求。

注意到我们每次只要考虑低位，可以忽略高位，所以前几步可以不需要&的操作，于是得到如下代码：

/* Return 1 when x contains an odd number of 1s;0 otherwise.
   Assume w=32 */
#include <stdio.h>

int odd_ones(unsigned x){
    //只考虑16位
    int a1 = (x ^ (x >> 16));
    //只考虑8位
    int a2 = (a1 ^ (a1 >> 8));
    //只考虑4位
    int a3 = (a2 ^ (a2 >> 4));
    //只考虑2位
    int a4 = (a3 ^ (a3 >> 2));
    //生成结果
    int res = (a4 ^ (a4 >> 1)) & 1;

    return res;
}

int odd_ones_(unsigned x){
    int res = 0;
    int cnt = 0;
    while (x != 0){
        cnt += x % 2;
        x /= 2;
    }

    return cnt % 2;
}

void test(){
    int start = -10000;
    int end = 10000;
    int flag = 1;
    for (int i = start; i <= end; i++){
        if (odd_ones(i) != odd_ones_(i)){
            flag = 0;
            break;
        }
    }

    if (flag){
        printf("Test pass!\n");
    }else{
        printf("Test fail!\n");
    }
}

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

总结

63,65比较有意思，可以多回顾几遍。

另外这里总结几个常用技巧。

技巧1

if (a == b){
	return 1;
}else{
	return 0;
}

等价于

return !(a ^ b);

技巧2

给定s(0或1)，如何生成

$$1\ldots 1,0\ldots0$$

方法如下：

//s=0时mask=1111，否则为1110
int mask = ~s;
//s=0时mask=0000，否则为1111
mask = mask + 1;