课程实验

CSAPP 2e Data Lab 笔记

本人环境：Ubuntu 22.04 LTS amd64，GCC 11.2.0，GNU Make 4.3

前言

这是《深入理解计算机系统》的第一个 Lab，要求以指定的方式完成某种计算，通过填写函数实现。

不要忘了阅读 bits.c 开头的 Integer Coding Rules 和 Floating Point Coding Rules，以及每题开头的要求，它规定了使用者可以执行的操作。

用二进制的思想，而不是十进制的思想，对完成题目有很大的帮助。

本笔记离不开参考资料的支持，我特意将其放至开头：

参考资料：

  1. https://github.com/Exely/CSAPP-Labs/blob/master/notes/datalab.md
  2. https://www.luogu.com.cn/blog/ACdreamer/lun-wei-yun-suan-chang-shuo-you-hua-di-sao-cao-zuo
  3. https://zhuanlan.zhihu.com/p/353348665
  4. https://blog.csdn.net/zjwreal/article/details/80925956

1. bitAnd

cpp 
1
2
3
4
5

int bitAnd(int x, int y)
{
  // Just discrete mathematics. XY=\overline{X+Y}.
  return ~((~x) | (~y));
}

计算 x&y，但只能用 ~ 和 | 运算符。

离散数学的基础关系代数知识，由德摩根律，$XY=\overline{X+Y}$。

2. getByte

cpp 
1
2
3
4
5

int getByte(int x, int n)
{
  int mask = 0xff;               // Leave only the last 2 bytes
  return (x>> (n << 3) & mask); // Right move 8n bits, i.e. n bytes
}

从 $x$ 中获取第 $n$ 位。

不要把 int x 当成一个整型了，直接想象它的二进制码。如果将指定位的左右两边全都去掉，这个数不就等于想要的单个位了吗？

去掉右边的数很容易，直接右移 $8n$ 位，这样想要的部分就直接到了最低位。而要去掉多余的高位，需要让它与 mask 按位与，来将高位置 0。

那，mask 是个什么来头？先说说子网掩码：如果有两个 IP 地址，将它们分别与子网掩码做按位与运算，若结果相同，则这两个 IP 地址在同一个网段中。mask 有类似的功能，具体来说，这里的 mask 转换为二进制是 1111 1111 1111 1111，如果作为一个 int 类型，前 24 位皆为 0。将这个数与任何一个 int 进行按位与，结果就是将前 24 位全部置 0 的原数，因为 $0\&x=0$，$1\&x=x$，其中 $x=0\ or\ 1$。后面我们还会使用这个设计。

3. logicalShift

cpp 
1
2
3
4
5
6

int logicalShift(int x, int n)
{
  int topMask = 0x1 <<(32 + ~n); // 32+~n=31-n, to get the top mask
  int lowerMask = (0x1 << (32 + ~n)) + ~0;
  return (x>> n) & (topMask | lowerMask);
}

对 $x$ 向右进行 逻辑 移位 $n$ 位。移位运算符采用的算术移位，在右移时补充的值与符号位相同，而算术移位一律补 0。

像上题一样，我们可以算术移 $n$ 位，然后使用一个掩码来让补上的部分强制置 0。这里参考了 参考资料 1 的做法，简略来说就是为了避免未定义的行为，分别构建了高位和低位的掩码。具体的可以直接看原文。

很多题目中是不允许我们使用减法的，我们可以使用取反加一的办法直接得到补码，如上面代码中 $31-n=32+~n$。这个方法在下面也经常用到。

4. bitCount

cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int bitCount(int x)
{
  int mask = (0x55) | ((0x55) <<8); // 0x00005555
  mask = mask | (mask << 16);        // 0x55555555
  x = (x & mask) + (x>> 1 & mask);  // 2-bit sum
  mask = (0x33) | ((0x33) <<8);     // 0x00003333
  mask = mask | (mask << 16);        // 0x33333333
  x = (x & mask) + (x>> 2 & mask);  // 4-bit sum
  mask = (0x0f) | (0x0f << 8);       // 0x00000f0f
  mask = mask | (mask << 16);        // 0x0f0f0f0f
  x = (x & mask) + (x>> 4 & mask);  // 8-bit sum
  mask = (0xff) | (0xff << 16);      // 0x00ff00ff
  x = (x & mask) + (x>> 8 & mask);  // 16-bit sum
  mask = (0xff) | (0xff << 8);       // 0x0000ffff
  x = (x & mask) + (x>> 16 & mask); // 32-bit sum
  return x;
}

统计 $x$ 所有二进制位中 $1$ 的数目。

首先想到的是 参考资料 2 中”2.2 统计 true 的数目“部分的解法，总体的思想是二分法，通过不断合并相邻两个分区的 1 数量，得到整体 1 的数量。与上面的代码不同，它直接将五个掩码写进了程序。

cpp 
1
2
3
4
5
6
7
8
9

int popcount(unsigned int x)
{
    x=(x&0x55555555)+(x>>1&0x55555555);
    x=(x&0x33333333)+(x>>2&0x33333333);
    x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
    x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
    x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
    return x;
}

将 0x55555555 转化为二进制，可以很容易得出它作为掩码的作用是只留下一个数中偶数位的部分（从 0 开始），其他置 0，而函数中第一个语句的作用，就是将奇数位移到右边的偶数位上相加，并得出结果。第 $n$ 位的值也可以看作第 $n$ 位这个区间有多少个 1，合并后。就是两位加起来有多少个 1。

然后，第二行的作用是将第 0-1 位的 1 个数与第 2-3 位合并，以此类推，得到 0-3 位、4-7 位，然后在第三行再进行合并…… 最后，将 0-15 位和 16-31 位合并，就是整个整型数的 1 个数。

配合下面的图可能能够更好地理解：

1

图源参考资料 2，侵删

但是如果你想在 datalab 中这么填，是通不过测试的，因为十六进制常数的范围是 $0x00$~$0xff$，也就是说如此大的掩码是无法直接使用的。所以，我们需要自行从两位 16 进制数构造 8 位 16 进制数。拿第一个 mask 举例：

cpp 
1
2

int mask = (0x55) | ((0x55) <<8); // 0x00005555
mask = mask | (mask << 16);        // 0x55555555

2 位 16 进制能充当 8 位二进制。先通过按位与和左移 8 位（二进制）的操作，生成低 4 位十六进制，然后再通过左移和按位与的操作，将其复制到高 4 位一份。这样，掩码就构建好了。如将其压缩到一句中，分别给予左移 24、16、8、0 位，则运算符数量会超过限制。

5. bang

cpp 
1
2
3
4
5
6
7
8
9

int bang(int x)
{
  x = (x>> 16) | x;
  x = (x>> 8) | x;
  x = (x>> 4) | x;
  x = (x>> 2) | x;
  x = (x>> 1) | x;
  return ~x & 0x1;
}

在不使用 $!$ 的情况下计算非 $x$。

非运算表现为，如果 $x$ 不为 0，则结果为 1，否则结果为 0。也就是说，只要有任何一个二进制位为 1，取非得到的结果就是 0，那么我们就可以将 $x$ 的所有位 “压缩 “到第 0 位。如果 $x$ 中含有 1，那么第 0 位就会是 1。

最后一个语句是将 $x$ 按位取反，然后只留最后一位。这样返回的就是取非的结果了。

6. tmin

cpp 
1
2
3
4

int tmin(void)
{
  return 1 << 31;
}

返回补码的最小值。

int 型能表示的最大正数是 $2^{31}-1$，而 $2^{31}$ 可以故意让其上溢出，就可以得到补码的最小值了。

7. fitsBits

cpp 
1
2
3
4
5
6

int fitsBits(int x, int n)
{
  int moveBits = 33 + ~n;                   // Equals to 32-n
  int result = (x << moveBits) >> moveBits; // Left move, and then right move
  return !(x ^ result);                     // If okay, result should be equal to x
}

如果 $x$ 能够用 $n$ 位补码表示，返回 1。

如果你使用新版本 Linux，可能会导致无法通过 btest 测试，换别人的正解代码也一样。如果遇到此问题，请使用老版本，实测 Ubuntu 12.04 LTS（Linux 3.10）可用。 此处的不同可能与下面的汇编代码不同有关：

2

既然题目想知道 $x$ 能否用 $n$ 位补码表示，那么就创造一个 $n$ 位补码的环境。具体地来讲，就是向左移，直到从第 31 位到原数最低位就是 $n$ 位。

如果这个数并不能用 $n$ 位补码表示，那么原数字的高位就会被 “挤掉”，而这样的数再右移，无法再恢复被挤掉的数字。如果能如此表示，那么这个数本身并不会受到任何损失；算术右移同样位数之后，就可以恢复原来的状态。

最后再将其与原数异或取反，就可以得到结果。

8. divpwr2

cpp 
1
2
3
4
5

int divpwr2(int x, int n)
{
  int bias = (x>> 31) & ((1 << n) + ~0);
  return (x + bias) >> n;
}

返回 $x/2^n$，向零舍入。

右移运算会向下舍入，而题目要求负数向上舍入。CSAPP 书中的解决方法是为负数添加一个 bias（偏置）值 $2^k-1$，这样右移的时候就可以向上舍入了。x>>31 正是为了判断正负，提取了符号位。

9. negate

cpp 
1
2
3
4

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

返回 $-x$。

计算补码，取反加一。

10. isPositive

cpp 
1
2
3
4

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

如果 $x$ 是一个正数，返回 1。

正数的符号位是 0，但符号位是 0 的也可能是 0。内部先判断” 是否 $x \le 0$“，然后取非，就得到了是否为正数。

11. isLessOrEqual

cpp 
1
2
3
4
5
6
7

int isLessOrEqual(int x, int y)
{
  int val = ((x + ~y) >> 31) & 1;
  x = x >> 31;
  y = y >> 31;
  return ((x & 1) | !y) & (((x & 1) & !y) | (val));
}

val 取的是 $x-y-1$ 的符号位，如果 $x>y$ 才会为 0（因为整型，$x \ge y+1$），否则为 1。1 是掩码，防止为负时右移补出来一堆不需要的 1。

然后是取 x 和 y 的符号位，掩不掩都行。

最后还要判断溢出的情况，如果 $x<0,\ y>0$ 则直接返回 1。

12. ilog2

cpp 
 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

int ilog2(int x)
{
  int mask;

  x = (x>> 1) | x;
  x = (x>> 2) | x;
  x = (x>> 4) | x;
  x = (x>> 8) | x;
  x = (x>> 16) | x;

  mask = (0x55) | ((0x55) <<8);     // 0x00005555
  mask = mask | (mask << 16);        // 0x55555555
  x = (x & mask) + (x>> 1 & mask);  // 2-bit sum
  mask = (0x33) | ((0x33) <<8);     // 0x00003333
  mask = mask | (mask << 16);        // 0x33333333
  x = (x & mask) + (x>> 2 & mask);  // 4-bit sum
  mask = (0x0f) | (0x0f << 8);       // 0x00000f0f
  mask = mask | (mask << 16);        // 0x0f0f0f0f
  x = (x & mask) + (x>> 4 & mask);  // 8-bit sum
  mask = (0xff) | (0xff << 16);      // 0x00ff00ff
  x = (x & mask) + (x>> 8 & mask);  // 16-bit sum
  mask = (0xff) | (0xff << 8);       // 0x0000ffff
  x = (x & mask) + (x>> 16 & mask); // 32-bit sum
  return x + ~0;
}

求 $log_2x$ 向下取整的值。

借鉴了 参考资料 3 的做法，思路更加清晰，容易理解。首先我们知道，一个数以二进制表示，最高 1 位所对应的 2 的次方，就是 $log_2x$ 向下取整的值。举个例子来说，$(45)_{10}=(101101)_2=(1 \times 2^5+0 \times 2^4+1 \times 2^3+1 \times 2^2+0 \times 2^1+1 \times 2^0)_{10}$，那么就有 $log_2 45 = log_2 32 + log_2 \frac{45}{32}=5+x$，其中 x 肯定是一个小于 1 的数。那么，一个可行的思路就是找到最高位的 1 是第几位减一，但直接逐位右移再判断并不是可行的方法，因为较低位也可能为 0，可能统计不到真正的最高位就以为是最高位了。所以，我们先把非最高位全都设成 1，然后再统计 1 的个数即可。

先是类似于第 5 题 “Bang”的做法，将高位 “折” 下来。与第五题不同，这里移动的位数从低到高，因为先移 16 位的话，并不能保证高 16 位中能够正确地设 1；相反的，第 5 题使用这种顺序则是可以的。

然后是第 4 题 “bitCount” 的做法，统计有多少个 1，就可以得知最高位的 1 是第几位（从 1 开始计）。不过，由于第 1 位代表 $2^0$，最后还要将结果减一。

以下三道题全都是浮点数的题了。虽然参数看似并不是浮点数类型，但是二进制表示上，仍然是一个浮点数。某种程度上，这也是在鼓励学习者用二进制的方式思考问题。这三道题相比之前的限制条件更少，比如运算符都可以用了，还可以使用条件和循环控制语句。

13. float_neg

cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

unsigned float_neg(unsigned uf)
{
  int c = 0x00ffffff;
  if ((~(uf << 1)) <c)
  {
    return uf;
  }
  else
  {
    return uf ^ (0x80000000);
  }
}

本题要求返回参数的相反数。如果参数是 INF，则返回参数本身。

难度主要在判断 INF 上。INF 的特征是指数域全为 1，尾数域不全为 0。一个可行的思路是通过比较指数域和尾数域的大小来区分是否为 INF，但符号位会干扰比较，虽然理论上可以使用四个端点值分别比较大小得出结论，但未免有点不优雅。所以，这里向左移一位把符号位去掉，取反，然后和 c 比较大小。现在，前 8 位是取反的指数域，后 23 位是取反的尾数域，最后一位是左移补上的 0。如果它是 NaN，则此时前 4 位必然是 0，后 24 位必然小于 0xffffff（或者 0xfffffe）。这样，只需要一次比较就可以搞定，非常优雅（确信）。

否则，就将最高位也就是符号位与 1 异或，就相当于取反了。

14. float_i2f

cpp 
 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

unsigned float_i2f(int x)
{
  int sign, exp = 0, frac = 0, i = 0;

  if (x == 0) // Two special situations, cannot be calculated normally
  {
    return 0;
  }
  if (x == 0x80000000)
  {
    return 0xcf000000;
  }

  sign = (x>> 31) & 1; // Get the sign bit & abs(x)
  if (sign)
  {
    x = -x;
  }

  i = 30; // Not 31 coz the top bit is always 0
  while (!(x>> i))
  {
    i--;
  }
  exp = i + 127; // Get the exponent. i is the E, unbiased

  x = x <<(31 - i);          // Left shift to clean zeroes, right shift to fit 23 bits...
  frac = (x>> 8) & 0x7fffff; // ...to get the fraction
  x = x & 0xff;
  frac += (x> 0x80) || ((x == 0x80) && (frac & 0x01)); // Round up if fraction is greater than 0.5
  if (frac>> 23)
  {
    exp++;
    frac = frac & 0x7fffff;
  }
  return (sign << 31) | (exp << 23) | frac;
}

将一个整形转化为浮点数格式。

建议直接看 参考资料 4。

15. float_twice

cpp 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

unsigned float_twice(unsigned uf)
{
  int uf_nosign;
  int sign = uf & 0x80000000;   // sign bit
  int exp = uf & 0x7f800000;    // exponent bits
  int fraction = uf & 0x7fffff; // fraction bits
  uf_nosign = uf & 0x7fffffff;  // remove sign
  if ((uf_nosign>> 23) == 0x0) // denormalized condition
  {
    uf_nosign = uf_nosign << 1 | sign;
    return uf_nosign;
  }
  if ((uf_nosign>> 23) == 0xff) // special numbers (NaN and infty)
  {
    return uf;
  }
  // if ((exp>> 23) + 1 == 0xff)
  if (exp == 0x7f000000) // exponent overflow
  {
    return sign | 0x7f800000;
  }
  // return sign | (((exp>> 23) + 1) <<23) | fraction;
  return sign | (exp + 0x800000) | fraction;
}

要求将浮点数 uf 乘 2。如果为 NaN，返回原参数。

使用了 参考资料 1 的做法，进行了一定的优化。首先，使用不同的掩码将符号、指数域和尾数域分别取出来。然后单独算出没有符号位的 $uf$，存到 uf_nosign 中。

第一个 if 语句判断的是指数域全为 0 的情况（需要右移 23 位，因为去掉尾数域之后仍然用 0 占位），也就是非规格化值。此时只需要将去掉符号位的 uf 左移一位，然后加上符号位（按位与），就可以得到想要的数。因为指数域全为 0，所以即使尾数域左移导致溢出，也会表现为指数域 + 1 而无其他危险后果，而这恰是我们想要的结果。

第二个 if 语句判断的是特殊值的情况。如果是 NaN，直接返回 uf 肯定没问题，正如题目所说；如果是无限大，那么它的两倍还是无限，还是应该返回原数。

规格化的话，大体思路就是将指数域 + 1。第三个 if 语句判断的是指数域溢出的情况。因为单精度指数域只有 8 位，所以如果指数域 + 1 已经是 $0xff$ 了，就不再表示一个正常的数了（变成特殊值）。

最后，排除了所有特殊情况，就是正常的规格化值，将阶码 + 1，拼上符号位和尾数就可以了。

有一些运算上的简化，通过预先的运算可以节省运算符的使用量，和上方被注释掉的语句是等效的，如果不能理解，可以看被注释的语句。