深入理解计算机系统（CS:APP) - Data Lab详解

发表于 更新于 分类于 ， 阅读次数：

关于CS:APP

《深入理解计算机系统》(Computer Systems: A Programmer’s Perspective;CS:APP)这本书作为CMU核心课程的核心教材，一直被众人所推崇。这本书的主要内容就如它的英文名称那样：以一个程序员的视角看待计算机系统（现在的中文书名翻译给人一种这本书非常精深的错觉）。实际上这本书的内容并没有太过于深入，并且一直都作为计算机科学与技术专业低年级的计算机基础课来开设。所需要的前置知识也不是很多，一般来说学习过C语言之后就可以看了，并不需要提前学习汇编（本书第三章会讲解汇编的基础内容）。但个人感觉在学习过王爽的8086汇编以后学习本书的汇编会顺利不少。

我在三月份时得知本书第三版的英文版即将出版就早早预订了（第三版中文翻译版早已出版），苦苦等待一个月以后终于如愿成为了这版CS:APP的第一批读者。

读这本书的感受第一就是非常地爽，可以说这本书可以引领你从表层的程序一直深入到计算机内部的运作方式中，里面对于一些概念的理解也是给人一种前所未有的透彻感觉（溢出的图形表示、补码的权值理解等等）都切中了问题的本质。

除了书本上的内容，CMU的课程官网上还提供了9个lab，这9个lab也一直深受CMU开设的课程的学生们的喜爱，在lab中我们可以将在各章中学习到的知识运用到解决一个有趣的问题中，并且通过自动化的评分机制评估对知识的掌握程度。这9个lab同样是这本书的核心内容。

Data Lab

实验代码见GitHub

简介

在严格限制的条件下实现简单的逻辑、补码、浮点数操作函数。

本lab旨在帮助学生理解C中各类型的位表示和操作符对数据的位级作用行为。

所用工具

VS Code-用于代码编写
gcc-用于编译

第一部分 整数

所编写的程序必须满足如下要求：

  1. 只能使用0-255的整型常数
  2. 只能使用函数参数与函数内声明的局部变量
  3. 只能使用如下单目操作符：! ~
  4. 只能使用如下双目操作符：& ^ | + << >>
  5. 最多只能使用有限个运算符（等于号、括号不计），可以认为使用的运算符个数越少得分越高
  6. 一些函数可能对操作符有更多的限制（在题目前以操作符限制给出）
  7. 禁止使用任何控制结构如 if do while for switch等
  8. 禁止定义或使用任何宏
  9. 禁止定义任何函数
  10. 禁止调用任何函数（除了可以使用printf输出中间变量，但提交时必须去掉）
  11. 禁止使用任何形式的类型转换
  12. 禁止使用int以外的任何类型（包括结构体、数组、联合体）

可以假设程序在如下环境的机器上运行：

  • 采用补码表示整型
  • 32位int
  • 执行算术右移
  • 右移超过类型的长度时的行为未定义

bitAnd

  • 要求：只用~ |实现x&y
  • 操作符限制：~ |
  • 操作符使用数量限制：8
  • 思路：略
1
int bitAnd(int x, int y) { return ~((~x) | (~y)); }

getByte

  • 要求：取出x中的n号字节

    编号从低位到高位从0开始

  • 操作符使用数量限制：6

  • 思路：将x右移n*8位之后取出低8位的值

1
int getByte(int x, int n) { return (x >> (n << 3)) & 0xff; }

logicalShift

  • 要求：将x逻辑右移n位（0<=n<=31)
  • 操作符使用数量限制：20
  • 思路：将x的最高位除去后右移n位（保证高位补0），然后使用|操作符手动将最高位移动到的位置置上x的最高位。
1
2
3
4
int logicalShift(int x, int n) {
    int a = 1 << 31;
    return ((x & ~a) >> n) | ((!!(x & a)) << (32 + ~n));
}

bitCount

  • 要求：统计x的二进制表示中1的数量

  • 操作符使用数量限制：40

  • 思路：

    做这道题参考了stackoverflow上的一个回答，核心思想是分治：

    1. 将所有位分成32组，一组中只有1位

    2. 将相邻两组合为一组，组中的数值为原来两组中的数值相加

    3. 重复第2步，直到合成只有1组，组中的数值即为结果

      用图片比较便于理解：

      可以看到最终的0x0000000F即为1的数量15

      该算法能成功的关键在于一开始中每组中的数值即为每组中1的数量，然后将相邻两组中的数值相加的过程就相当于将之前一级的1的数量汇总，不断重复这个过程就可以将1的数量汇总到最后的一个数中。

      有了算法我们还要考虑如何在题目的限制条件下实现这一算法。

      为了实现将相邻两组中的值相加并放在合适的位置，我们采用掩码+位移的方式，例如有掩码：

      int mask1 = 0x55555555 (0101...0101)

      那么x = x & mask1 + (x >> 1) & mask1;实现了相加的过程，前面一部分先取出了一半的组，右移后再取出的就是后一半的组，再由按位相加的特点，它们相加后的值就存放在特定的位上（可以参照上面的图理解这一过程）。

      接下来只要使用不同的掩码和不同的位移就可以一步步实现这一过程。

      但是题目限制中我们只能使用0x00-0xFF的整型值，所以掩码也需要我们进行构造。

      答案如下，注意到当剩下4组，每组8位的时候我们就可以直接位移相加再取出低8位得到它们的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int bitCount(int x) {
    // referenced :
    // https://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators
    int mask1 = 0x55;
    int mask2 = 0x33;
    int mask3 = 0x0F;
    int result = 0;
    mask1 = mask1 | (mask1 << 8);
    mask1 = mask1 | (mask1 << 16);
    mask2 = mask2 | (mask2 << 8);
    mask2 = mask2 | (mask2 << 16);
    mask3 = mask3 | (mask3 << 8);
    mask3 = mask3 | (mask3 << 16);

    result = (x & mask1) + ((x >> 1) & mask1);
    result = (result & mask2) + ((result >> 2) & mask2);
    result = (result & mask3) + ((result >> 4) & mask3);
    return (result + (result >> 8) + (result >> 16) + (result >> 24)) & 0xff;
}

bang

  • 要求：不使用!实现!操作符

  • 操作符限制：~ & ^ | + << >>

  • 操作符使用数量限制：12

  • 思路：

    !操作符的含义是0变为1，非0变为0，我们自然可以想到要做的是区分非零和零，零相对的非零数有一个非常明显的特征是-0=0，而对于非零数，取负后必定是一正一负而不可能相等，利用这一点，可以得出非零数与它的相反数进行|运算后符号位一定为1，我们将符号位取出并取反就可以返回正确的值。

1
int bang(int x) { return 1 & (1 ^ ((x | (~x + 1)) >> 31)); }

tmin

  • 要求：返回补码表示的整型的最小值
  • 操作符使用数量限制：4
  • 思路：按照补码的权值理解，只要将权为-32的位置为1即可
1
int tmin(void) { return 1 << 31; }

fitBits

  • 要求：如果x可以l只用n位补码表示则返回1，否则返回0

    1 <= n <= 32

  • 操作符使用数量限制：15

  • 思路：

    如果x可以用n位补码表示，那么左移多余的位的个数后再右移回来的数值一定与原值相等，这个方法利用了左移后溢出的位会被丢弃，而右移回来时的是补符号位，如果丢弃了1或者右移时补的是1都会导致值的改变，而这两种情况也正说明了x不可以只用n位补码表示。

1
2
3
4
int fitsBits(int x, int n) {
    int a = 33 + ~n;
    return !((x << a >> a) ^ x);
}

divpwr2

  • 要求：计算x/(2^n) 0 <= n <= 30 结果向零取整

  • 操作符使用数量限制：15

  • 思路：对于正数，我们直接把x右移n位就可以得到向零取整的结果（实际上是向下取整）；对于负数，虽然我们右移n位可以得到结果，但是这个结果是向下取整的，所以我们需要适当地加上1来补为向零取整，那么我们什么时候需要加1呢？整除时当然不用，在不能整除时就都需要加上1来调整，如何判断是否整除？只要移出的位中有一个不为0，那么就表示无法整除。​

    1
    2
    3
    4
    5
    6
    int divpwr2(int x, int n) {
        int a = 1 << 31;
        int isALessThanZero = !!(x & a);
        int isXHasMoreBit = (!!((~(a >> (32 + ~n))) & x));
        return (x >> n) + (isXHasMoreBit & isALessThanZero);
    }

    negate

  • 要求：计算-x

  • 操作符使用数量限制：5

  • 思路：略。

    1
    int negate(int x) { return ~x + 1; }

    isPositive

  • 要求：如果x大于0返回1，否则返回0

  • 操作符使用数量限制：8

  • 思路：检测符号位与x是否为0即可。

    1
    int isPositive(int x) { return !((x & (1 << 31)) | !x); }

    isLessOrEqual

  • 要求：如果x小于等于y则返回1，否则返回0

  • 操作符使用数量限制：24

  • 思路：本题的基本思路是判断x-y得到的值是否小于等于0，但是要考虑溢出带来的影响，首先定义了两个变量xp,yp分别表示x,y是否大于等于0。return的表达式的含义为并并非x大于等于0且y小于0的情况下（&的后半部分），如果x-y小于或等于0或x小于零且y大于等于0，则返回1。

    1
    2
    3
    4
    5
    6
    7
    int isLessOrEqual(int x, int y) {
        int t = 1 << 31;
        int xp = !(x & t);
        int yp = !(y & t);
        int p = x + ~y + 1;
        return (!!(((!xp) & yp) | ((p & t) | !p))) & (!(xp & (!yp)));
    }

    ilog2

  • 要求：返回x求以2为底的对数的结果 向下取整

  • 操作符使用数量限制：90

  • 思路：本题参照了陈志浩学长的答案。
    解题算法的核心思想是二分查找，首先我们要明白这道题实际上想让我们求的是什么，经过观察我们可以得出结论，一个数求以2为底的对数的结果就相当于它二进制中位置最高的1的序号（序号从零开始由低位到高位）。那么我们需要做的就是查找并记录这个位置最高的1的位置。
    算法过程如下：

    1. 如果x >> 16的结果大于0，那么可以说明最高位的位置至少是16，那么我们可以将结果的第4位置1（序号编号规则同上），因为2 ^ 4 = 16，反之置0说明结果小于16.
    2. 下面考虑两种情况，如果第1步中x >> 16 大于0，说明我们需要在16位之后的第8位（第24位，相当于再二分）再进行二分查找，如果x >> 16小于0，那我们需要在16位之前的第8位（第8位，相当于再二分）进行查找，那么我们可以得出，下次查找时的范围为x >> (8 + result) (result表示上一步得到的结果（0或16）)，这个+result的意义可以认为是重新确定开始进一步二分查找的位置。
      如果x >> (8 + result) 的结果大于0，那么说明结果（result)的第3位必为1，相当于在结果上加上了查找到的新位置，反之第3位应该仍为0.
    3. 按照上面的思路继续查找到不能再二分（偏移为x >> (1 + reuslt)），此时result中得到最终的最高位的位置。
      算法描述起来比较难，参照代码推理几次就可以明白其中的巧妙之处：
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      int ilog2(int x) {
          int result = 0;
          int b4 = !!(x >> 16);
          int b3 = 0;
          int b2 = 0;
          int b1 = 0;
          int b0 = 0;
          result = b4 << 4;
          b3 = !!(x >> (8 + result));
          result = result | (b3 << 3);
          b2 = !!(x >> (4 + result));
          result = result | (b2 << 2);
          b1 = !!(x >> (2 + result));
          result = result | (b1 << 1);
          b0 = !!(x >> (1 + result));
          result = result | b0;
          return result;
      }

      第二部分 浮点数

所编写的程序必须满足如下要求：

  1. 只能使用函数参数与函数内声明的局部变量
  2. 最多只能使用有限个运算符（等于号、括号不计），可以认为使用的运算符个数越少得分越高
  3. 禁止定义或使用任何宏
  4. 禁止定义任何函数
  5. 禁止调用任何函数（除了可以使用printf输出中间变量，但提交时必须去掉）
  6. 禁止使用任何形式的类型转换
  7. 禁止使用int、unsigned以外的任何类型（包括结构体、数组、联合体）
  8. 禁止定义或使用任何浮点常量

也就是说在浮点数题目中，我们可以使用任意大小的整型数值，可以使用流程控制语句，可以使用任何操作符。

float_neg

  • 要求：返回-f的位级表示

    本题及以下所有的题目都采用unsigned int来存放位级表示

    所有的浮点类型都为float

    如果输入为NaN，返回NaN

  • 操作符使用数量限制：10
  • 思路：对于一般的浮点数，我们只需要对它的符号位取反就可以了。需要特殊处理的只是无穷与NaN这两种非规格化的情况
1
2
3
4
5
6
7
unsigned float_neg(unsigned uf) {
    unsigned result = uf ^ 0x80000000;
    if ((uf & 0x7F800000) == 0x7F800000 && (uf & 0x007FFFFF)) {
        result = uf;
    }
    return result;
}

float_i2f

  • 要求：实现由int到float的类型转换

  • 操作符使用数量限制：30

  • 思路：

    由于浮点数的表示中对于负数并没有使用补码的方式，正负号完全取决于符号位，所以对于负数输入，我们需要做的第一步工作就是把它取负为正数再进行后面的操作。在这个过程我们需要记录下正负，在之后的操作中需要使用。

    由于浮点数与整数表示的不同，浮点数的有效数字的位置在第0-22位的23位中，并且第一个1在规格化表示中会被省略，我们只需要第一个1以后的位数，并且我们需要知道在浮点数表示中它的指数应该为多少，所以在这个过程中我们同时需要记录第一个1出现的位置并以此决定指数。

    在代码中使用了一个i来记录左移的位数，也就是最高位的1之前的零的个数，那么32-i就是最后的指数。

    在循环中我们将整数的有效数字提前到了最前，然后将最高位移出， 这时我们用temp保存这时的状态。供之后的舍入判断使用。

    接下来，我们需要将有效位移到正确的位置上，也就是向右位移9位。

    下面按照之前的记录把符号位置上正确的值。

    现在已经处理好有效数字与符号部分，下面要做的就是处理指数部分。

    之前说过32-i是指数的数值，注意我们需要将这个值加上偏移量127，再放入表示指数的位置中。

    下面就要处理舍入的情况了，浮点数表示的舍入规则比较特殊，也是本题的难点。结合本题的情况进行介绍：

    在右移之前我们保存了这时的状态，因为当右移九位后原来的低九位如果有数据就会被舍弃，我们就需要根据舍弃的这九位与未被舍弃的最后一位（也就是原数第9位，下称第9位）来判断舍入的情况。

    如果舍弃的这九位的最高位为0，那么说明舍去的数值小于保留下来的最低位表示的值的二分之一，那么我们不需要舍入。

    如果舍弃的这九位的最高位为1，并且后面的位有数值，那么说明舍去的数值大于第9位表示的值的二分之一，这个时候我们需要舍入，也就是把最终结果加一。

    如果舍弃的这九位的最高位为1，并且后面的位都是0，这个时候正好就是第9位表示的值的二分之一。那么这个时候我们就要看第9位，如果第9位为0，那么不舍入。如果第9位为1，那么进行舍入，也就是把最终结果加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
unsigned float_i2f(int x) {
    int i = 1;
    int nega = 0;
    unsigned temp;
    unsigned result;

    if (x & 0x80000000) {
        nega = 1;
        x = ~x + 1;
    }
    if (x == 0) {
        return 0;
    }
    while ((x & 0x80000000) != 0x80000000) {
        ++i;
        x <<= 1;
    }
    result = x << 1;
    temp = result;
    result >>= 9;
    if (nega) {
        result |= 0x80000000;
    } else {
        result &= 0x7FFFFFFF;
    }
    i = (32 - i) + 127;
    result = (result & 0x807FFFFF) | (i << 23);
    if ((temp & 0x00000100) == 0x00000100) {
        if (temp & 0x000000FF) {
            return result + 1;
        } else {
            if (result & 1) {
                return result + 1;
            } else {
                return result;
            }
        }
    }
    return result;
}

float_twice

  • 要求：返回2*f的位级表示

  • 操作符使用数量限制：30

  • 思路：

    如果该浮点数是非规格化的，那么我们需要将它的有效数字部分左移一位就可以达到乘二的效果，这个过程需要注意两个地方，第一是如果左移后如果有效数字的最高位溢出了，那么正好移到了指数部分成为了一个规格化的表示形式，所以我们无需担心左移后有效数字溢出的问题。第二是左移后会导致符号位被移出，我们需要在位移之后手动置上原来的符号位。

    如果该浮点数是规格化的，那么我们只需要将它的指数部分加一。

    其他情况的应该直接返回原值。

1
2
3
4
5
6
7
8
9
unsigned float_twice(unsigned uf) {
    unsigned result = uf;
    if ((uf & 0x7f800000) == 0) {
        result = ((uf & 0x007fffff) << 1) | (uf & 0x80000000);
    } else if ((uf & 0x7f800000) != 0x7f800000) {
        result = uf + 0x00800000;
    }
    return result;
}

实验小结

作为CS:APP的第一个lab，绝大部分的题目在经过仔细思考与测试后是可以自主完成的，但是其中的bitCount与ilog2由于需要使用分治与二分查找的算法，自己想出来的难度还是比较大的，在卡了两天以后还是去查了答案。