吴锴的博客

Life? Don't talk to me about life!

0%

《深入理解计算机系统 CSAPP》Data Lab 记录

发表于

《深入理解计算机系统 CSAPP》这本书我已经买了很多年了，一直都只是翻翻而已，阅读进度常年在前两章。趁着最近有时间，再次拿出了这本书，准备好好学习一下。配套的几个 lab 也试着做一下，这篇文章就是记录一下第一个 data lab 的过程。

Lab 的环境准备

这是 CSAPP Lab 的官方网站，上面有各个 lab 详细介绍和下载地址。

Lab 正常运行和测试需要安装相应的环境，利用 docker 可以省去配置环境的环节，我使用的这个已经制作好的 docker 镜像：项目地址。在安装 docker 之后，按照项目 README 的步骤 clone 项目并启动即可。这个项目中已经包含了所有的 lab 文件，因此不需要额外下载了。

Docker 启动命令如下：

1
docker run -p 7777:7777 -v "$PWD/labs:/home/csapp/project" xieguochao/csapp

然后在浏览器中打开 http://localhost:7777 即可。

-v 参数是将本地的 labs 目录挂载到 docker 容器中，容器内部的目录路径是 /home/csapp/project 是容器内部的目录路径，这样在容器中修改的文件也会同步到本地。如果想再挂载一个目录，比如建立了一个和 labs 目录同级的 learn 目录，用于放置一些测试代码，可以再添加一个 -v 参数：

1
docker run -p 7777:7777 -v "$PWD/labs:/home/csapp/labs" -v "$PWD/learn:/home/csapp/learn" xieguochao/csapp

Data Lab 的目标

Data Lab 要完成的目标可以查看它的文档：datalab。

简要来说：这个 lab 是考察你对各种位运算和数据表示的理解，bits.c 中给出了一些函数，需要你在给定的限制下将函数实现补充完整。

改动 bits.c 文件后，通过以下命令来测试：

1
2
3
4
5
make
# 运行后能看到你的分数
./btest
# 也可以单独测试一个函数
./btest -f bitXor

使用 ./dlc bits.c 检查是否有不允许使用的运算符。

虽然我作为一个前端开发，在工作中直接使用位运算的情况并不多，但是这个 lab 拿来练习并补充知识盲区是不错的。

题目解析

bitXor

1
2
3
4
5
6
7
8
9
10
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(x & y) & (~(~x & ~y));
}

说明：

异或运算 ^ 结果为真就是 x 和 y 中有且有一个为真， x ^ y = (x & ~y) | (~x & y)。因为题目要求不允许使用 |，所以需要使用德摩根定律转换一下，将表达式中的 | 转换成 &。

tmin

1
2
3
4
5
6
7
8
9
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1 << 31;
}

说明：

最小的补码数，就是最高位为 1，其余位为 0 的数，将 1 左移 31 位即可。

isTmax

1
2
3
4
5
6
7
8
9
10
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  return !~(x + 1 + x) & !!(x + 1);
}

说明：

最大的补码数，就是最高位为 0，其余位为 1 的数。

它与上一题的 tmin 所有位均不同，如果将两个数异或，得到的应该是一个全 1 的位表示。

1
!~((1 << 31) ^ x);

但是这一题中我们不能使用移位，所以需要换一个思路。

对于 tmax 可以计算 x + 1 + x 得到一个全 1 的数，取反后得到全 0 的数。但是有一个特殊情况，就是 x = -1 的时候（即所有的位均为 1），x + 1 + x 会溢出，取反后它也会得到全 0 的表示，还需要排除这种情况。

allOddBits

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  int y = x & (x >> 8) & (x >> 16) & (x >> 24);
  int mask = 0xAA;
  return !((y & mask) ^ mask);
}

说明：

A 的二进制表示为 1010，易得 0xAAAAAAAA 的所有奇数位都是 1。如果 x 的所有奇数位都是1，将 x 与 0xAAAAAAAA 进行与操作后，得到的结果应该是 0xAAAAAAAA。

1
2
int mask = 0xAAAAAAAA;
return (x & mask) == mask;

因为不允许使用 == 来判断相等，可以改用异或来判断是否相等，一个数和它本身的异或结果为 0。

1
2
int mask = 0xAAAAAAAA;
return !((x & mask) ^ mask);

改动之后仍然存在一个问题，我们允许定义的常量最大为 0xFF，所以不能直接使用 0xAAAAAAAA，可以定义常量 0xAA，通过移位来判断每8位是否都符合要求。

1
2
3
int y = x & (x >> 8) & (x >> 16) & (x >> 24);
int mask = 0xAA;
return !((y & mask) ^ mask);

negate

1
2
3
4
5
6
7
8
9
10
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}

说明：

~x + x 一定是全 1 的表示，+1 后会溢出得到 0，所以 x + (~x + 1) == 0。可以得出补码数的相反数，就是取反加一。

isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  int sign = 0x1 << 31; // 获取int类型的最高位，即符号位
  int upperBound = ~(sign | 0x39); // 上界，大于 0x39 的数与之相加后变为负数
  int lowerBound = ~0x30 + 1; // 下界，-x，小于 0x30 的数与之相加后为负数

  // 判断x是否小于下界
  int isLessThanLowerBound = sign & (lowerBound + x) >> 31;

  // 判断x是否大于上界
  int isGreaterThanUpperBound = sign & (upperBound + x) >> 31;

  return !(isLessThanLowerBound | isGreaterThanUpperBound);
}

说明：

这道题的思路是找到数字范围对应的上下界。

数字中最大的值是 0x39，它会有对应的一个上界，0x39 + 上界 得到最大的正数（即除符号位外均为 1）。假如 x > 0x39，则 x + 上界 会溢出得到一个负数。 可以利用 x 与上界相加后的符号位来判断。

数字中最小的值是 0x30，它会有对应的一个下界，0x30 + 下界 得到 0。假如 x < 0x30，则 x + 下界 会得到一个负数。 可以利用 x 与下界相加后的符号位来判断。

以 4 位数字来举例说明，能表示的最大的正数是 \([0111]_2\) ，想确定一个数字是否大于数字 \(3 = [0011]_2\) ，找出 3 对应的上界是 \([0100]_2 = 4\)，大于 4 的数与 3 相加后都会变为负数。因为二者相加得到了除符号位外全 1 的数字，所以要找到一个数字对应的上界只要将其除符号位的各位取反即可，符号位保持为0。

conditional

1
2
3
4
5
6
7
8
9
10
11
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  int mask= ~!x+1; 
  return (y & ~mask) | (z & mask);
}

说明：

返回的结果是 y 和 z 中的一个，表达式应该是这样的形式 (y op expr) | (z op expr)

我们需要这样的一个掩码值（表格中以16位为例）：

x mask y & ~mask z & mask
0 0xffff 0x0000 z
非0 0x0000 y 0x0000

这个掩码值可以通过表达式 ~!x + 1 根据 x 的不同情况来求出：

x !x ~!x ~!x + 1
0 0x0001 0xfffe 0xffff
非0 0x0000 0xffff 0x0000

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
  int diff = ~x + 1 + y;
  int signD = diff >> 31 & 0x1;
  int signX = x >> 31 & 0x1;
  int signY = y >> 31 & 0x1;
  int sameSign = !(signX ^ signY);
  return (sameSign && !signD) | (!sameSign & signX);
}

说明：

比较大小需要区分 x 和 y 的符号是否相同。符号相同，比较差值；符号不同，需要满足 x < 0。

为什么要区分符号相同和符号不同的情况呢？假设是 8 位二进制表示的数字，补码表示的范围是 [-128, 127]。x 和 y 的值如下：

1
2
x = 0x80; // -128
y = 0x7f; // 127

y - x = 255，这个值在 8 位二进制补码表示的是 -1，但是 y > x。所以需要区分符号相同和符号不同的情况。

当二者符号相同时，x <= y 即 y - x >= 0，y - x 使用 ~x + 1 + y 来计算，如果符号位是 0 则表示满足。

logicalNeg

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  int a = x | (~x + 1); // x | -x
  int sign = a >> 31; // 算术右移
  return sign + 1;
}

说明：

除了 0 以外，一个数和它的相反数一定是一正一负，因此利用 x 和 -x 的符号位可以得到结果。

howManyBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int howManyBits(int x) {
  int sign = x >> 31;
  // 对于正数保持不变，对于负数各位取反
  int y = x ^ sign;
  // 检查高16位是否有值，如果有的话，则至少需要16位。
  // 高16有值，设置 bit_16 = 16，右移16位，检查具体最高位在哪
  // 高16没有值，bit_16 = 0，无需右移，开始检查低16位
  int bit16 = !!(y >> 16) << 4;
  y = y >> bit16;
  int bit8 = !!(y >> 8) << 3;
  y = y >> bit8;
  int bit4 = !!(y >> 4) << 2;
  y = y >> bit4;
  int bit2 = !!(y >> 2) << 1;
  y = y >> bit2;
  int bit1 = !!(y >> 1);
  y = y >> bit1;
  int bit0 = y;
  return bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1;
}

说明：

对于正数，符号位为0，关键在于找到最高位的1的位置，然后加上一个符号位。

对于负数，最高位一定是1，而最高位的若干个连续的1可以等价于1个单独的1（符号扩展）。

比如 \(1110_2 = -8 + 4 + 2 = -2\)，它和 \(10_2 = -2\) 是相等的。

因此，关键在于找到最高位的零的位置，如果我们将负数各位取反，则思路和正数一致了，都是需要确定最高的 1 的位置。

假设对于最大的正整数：2^31-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
0111 1111, 1111 1111, 1111 1111, 1111 1111
↑                  ↑
高16位有值 bit16 = 16
将高16位移动至低16位

0000 0000, 0000 0000, 0111 1111, 1111 1111
                      ↑       ↑
高8位有值，bit8 = 8
将高8位移动至低8位

0000 0000, 0000 0000, 0000 0000, 0111 1111
                                 ↑  ↑
高4位有值，bit4 = 4
将高4位移动至低4位

0000 0000, 0000 0000, 0000 0000, 0000 0111
                                      ↑↑
高2位有值，bit2 = 2
将高2位移动至低2位

0000 0000, 0000 0000, 0000 0000, 0000 0001
                                        ↑
高1位没有值，bit1 = 0
不移动，检查最后一位

0000 0000, 0000 0000, 0000 0000, 0000 0001
                                         ↑
bit0 = 1

假设对于2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000 0000, 0000 0000, 0000 0000, 0000 0010
↑                  ↑
高16位没有值，bit16 = 0，不右移

0000 0000, 0000 0000, 0000 0000, 0000 0010
                      ↑       ↑
高8位没有值，bit8 = 0，不右移

0000 0000, 0000 0000, 0000 0000, 0000 0010
                                 ↑  ↑
高4位没有值，bit4 = 0，不右移

0000 0000, 0000 0000, 0000 0000, 0000 0010
                                      ↑↑
高2位没有值，bit2 = 0，不右移

0000 0000, 0000 0000, 0000 0000, 0000 0010
                                        ↑
高1位有值，bit1 = 1，右移1位

0000 0000, 0000 0000, 0000 0000, 0000 0001
                                         ↑
bit0=1

floatFloat2Int

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
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 * for floating point argument f.
 * Argument is passed as unsigned int, but
 * it is to be interpreted as the bit-level representation of a
 * single-precision floating point value.
 * Anything out of range (including NaN and infinity) should return
 * 0x80000000u.
 * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 * Max ops: 30
 * Rating: 4
    */
   int floatFloat2Int(unsigned uf) {
     int sign = uf >> 31;
     int exp = uf >> 23 & 0xFF;
     int frac = uf & 0x7FFFFF;
     int E = exp - 127;

  if (exp == 255 || E > 30) {
    return 0x80000000u;
  }
  if (!exp || E < 0) {
    return 0;
  }

  int result = 1 << E; // 在小数的开头加上一个1
  if (E < 23) {
    result |= frac >> (23 - E); // 舍去小数点右侧的数字 
  } else {
    result |= frac << (E - 23); // 在小数右侧补零
  }

  if (sign) {
    result = ~result + 1;
  }

  return result;
}

说明：

根据浮点数的表示依次处理符号位、指数部分、小数部分即可。

具体说明可以参考这一篇：Converting float to int in C

floatPower2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
  int exp = x + 127;
  if (exp <= 0) return 0;
  if (exp >= 255) return 0xFF << 23; // 指数位均为1表示无穷大
  return exp << 23; // 把指数位放到正确的位置
}

说明：

在浮点数表示中，指数部分就代表了是 2 的多少次幂，将 x 加上偏置值得到指数部分，然后左移至正确位置即可。

参考资料

我在完成这个 lab 的时候参考了别人的实现方案，以下是一些给了我帮助的文章：

如果我的文章对你有帮助，欢迎打赏支持！

欢迎关注我的其它发布渠道