CSAPP - Data Lab

Computer Systems: A Programmer’s Perspective, 3/E (CS:APP3e) – Data Lab，实现源码可从 HangX-Ma/csapp: 01-datalab 获取。

Progress and timeline [1/14]

Prerequisite

WSL2, Ubuntu-20.04
gcc, gcc-multlib, gdb, build-essential, make

64 位机器编译时，由于库不支持 32 位代码编译，因而需要下载 gcc-multilib。

sudo apt install build-essential make
sudo apt install gcc gcc-multilib gdb

题解与分析

1. bitXor

/*
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  int a = ~x & y;
  int b = x & ~y;
  return ~(~a & ~b);
}

参考数字逻辑电路部分的异或门，逻辑表达式为 $A \oplus B = \overline{A}B + A\overline{B}$，需要对这部分进行变式推导，主要应用了反演律（摩根定律） $\overline{A}B + A\overline{B} = \overline{\overline{\overline{A}B + A\overline{B}}} = \overline{\overline{\overline{A}B} \bullet \overline{A\overline{B}}}$。当然更简单的是根据同或门取反实现。

2. tmin

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

32 位机最小的补码是 0x80000000，既然能用 << 操作符就直接向左移位 31 位。

3. isTmax

/*
 * 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 + 1) ^ x);
}

由于不能使用移位操作符，需要用替代办法实现。以 4 位 $TMax_4 = 0111_2$ 为例， $TMax_4 + 1 = 1000_2$，该数取反也会得到 $TMax_4$，那么以 !（~(x + 1) ^ x) 就可以满足要求。但是用 btest 检查的时候却报错如下，发现 -1 这个例外同样满足上式。但发现存在 -1 + 1 = 0 这个特殊性质，故而可以借此进行两数的区分， !(x + 1) 若为零则说明输入 x 是除 -1 以外的数。

ERROR: Test isTmax(-1[0xffffffff]) failed...
...Gives 1[0x1]. Should be 0[0x0]

4. allOddBits

/*
 * 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 mask = 0xAA;
  int mask_all = (mask | (mask << 8) | (mask << 16) | (mask << 24));
  x &= mask_all;
  x ^= mask_all;
  return !x;
}

属实有点被坑到，说是要求不能用超过 8 位的常量，但实际上可以通过这样取巧的方式定义一个，具体实现也比较简单，用掩码解决。

5. negate

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

x + ~x = -1 因而 -x = ~x + 1，需注意补码，反码，原码之间的关系。

6. isAsciiDigit

/*
 * 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 hbits_fit = (x >> 4) ^ 0x3;
  int lbits_fit = ((x & 0xF) + (~0xA + 1)) & (1 << 31);

  return (!hbits_fit) & !!lbits_fit;
}

0x30 = 0011 0000 以及 0x39 = 0011 1001 可以看出 0011 也就是 0x3_ 部分对于二者而言是一致的，因而 x >> 4 == 3 是首要的判断条件。另外就是保证末尾 4 位位于 0 ~ 9 之间即可。那么首先通过 & 0xF 运算读取最后 4 位的数据，根据前面的 negate 实现方式使 0xA 成为负数方便做差，若结果是负数则说明尾数在范围之内。

7. conditional

/*
 * 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 ifTrue = !!x;
  int cond = ~ifTrue + 1;
  int neg_y = ~(y & ~cond) + 1;
  int neg_z = ~(z & cond) + 1;
  return y + neg_y + z + neg_z;
}

判断 x 的属性是第一优先级， !!x 可以将其转换为 0 和 1 两个数。这步判断也比较关键，若为 1 则返回 y 反之则返回 z，故而需要利用对 x 的判断结果。

需要依据判断结果消除 y 或 z 对结果的影响。
-y 和 -z 与前述结果进行条件加和可以达到目的。

可知对 0 和 1 分别取反可以得到 0xFFFFFFFF 以及 0xFFFFFFFE，若再加上 1 则可以得到 0x00000000 与 0xFFFFFFFF，这个结果正是进行条件选择的依据。利用 & 操作符即可选择 -y 与 -z 之一为 0，则该数对后续返回值不会造成影响。

8. isLessOrEqual

/*
 * 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 neg_x = ~x + 1;
  int isLess = !((neg_x + y) >> 31);
  int isEqual = !(x ^ y);
  // we don't know right shift is logical or arithmetic.
  int sign_x = (x >> 31) & 0x01;
  int sign_y = (y >> 31) & 0x01;
  int negxy = sign_x & ~sign_y;
  int negyx = ~sign_x & sign_y;

  return negxy | (!negyx & isLess) | isEqual;
}

可以容易得到 -x 以及关于 -x + y 的比较关系，也就是上式中的 neg_x 和 isLess。

若 x 为负数，而 y 为正数，显然 x < y。但在 isLess 的判断式中可能会产生溢出导致相反的结果。那么索性将这部分的判断交由两数的符号而不使用 isLess 判断式。因而当 negxy 为 1 就无需判断后续的表达式。
若 x 为正数，而 y 为负数，显然 x > y，那么只需要返回 !negyx 就可避免溢出。
x 与 y 同号时交予 isLess 判断即可，但这个判断是与 negyx 或者 negxy 相关联的，因而需要选其一进行相与操作，否则前两点叙述中对 后续部分无需判断 的叙述就不成立了。
另外额外考虑两者相等，通过异或操作符即可判断。

9. logicalNeg

/*
 * 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 ifzero = (~((~x + 1) >> 31) & 0x01) & (~(x >> 31) & 0x01);
  return ifzero;
}

要求除了 ! 操作符外，使用任何其他的操作符来实现 ! 的效果。 0 这个数取负仍然是其本身，因而可以利用这个特点，对符号位进行判断。由于我们需要在输入为 0 时返回 1，以及输入非零时返回 0，因而对所获取的符号位需要再取反。除了 0 以外的数其负数和正数的符号必然相异，据此即可得到结果。

10. howManyBits

/*
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 */

需要分析 example 中所表达的意思，对于正数而言其实不难推导， 12 = 1100 但返回的位数为 5，说明对于正数其实是加上了符号位，那么只需要找到最高位的 1 即可知道该数用补码表示的位数为 n+1 位，其中 n（1~31） 为 1 所在位置。

但是负数部分着实有些迷惑，看来看去都像是取负之后的结果。比如 -5 取负后为 5 = 0101 加上符号位正好结果为 4。但是 -1 和 0 的结果都为 1 说明对于这两个特殊数字而言符号位是不需要加上的，那么同理若输入为 1 也不需要。（在具体实现中满足了这点要求）

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int div16, div8, div4, div2, div1, remain;
  int sign = x >> 31;
  /* get positive x */
  x = ((~sign) & x) | (sign & (~x));
  /* some bits set among high 16 bits or not */
  div16 =  !!(x >> 16) << 4;
  x = x >> div16;
  div8 =  !!(x >> 8) << 3;
  x = x >> div8;
  div4 =  !!(x >> 4) << 2;
  x = x >> div4;
  div2 =  !!(x >> 2) << 1;
  x = x >> div2;
  div1 = !!(x >> 1);
  x = x >> div1;
  remain = x;
  return 1 +  div16 + div8 + div4 + div2 + div1 + remain;
}

利用分治法，这部分借鉴了网上的代码。例如 div16 实际上就是判断高 16 位是否存在为 1 的 bit，若存在则至少有 16 位，那么接着在高 16 位进一步分治。否则，在 [16， 8] 之间进行 8 位的分治依次类推。最差的情况是 [32, 16], [16, 8], [8, 4], [4, 2], [2, 1] 这些区间内都需要进行判断。

11. floatScale2

Float32 format, CSAPP, Figure 2.32

Categories of single-precision floating-point values, Figure 2.33

根据书中所描述的 float32 的定义，需要将输入的 uint32 的数拆分成符号位 S(31)，指数位 exp(23-30)，以及小数位 frac(0-22) 并根据这些数的值区分 Normalized， Denormalized, 以及特殊类型 Infinity, NaN。

\[V = (-1)^{S} \times M \times 2^{E}\]

对于此道题而言，输入 uf 需要返回 2 * uf，根据上述公式， E 的值应当加 1。

/*
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  unsigned sign = uf & (0x80000000);
  unsigned exp = uf & (0x7F800000); // 8 bits

  if (!(exp ^ 0x7F800000)) {
    return uf;
  } // NaN or Infinity

  exp = exp >> 23; // acquire exp

  if (exp == 0) {
    return (uf << 1) | sign; // only M and S remain
  }
  exp = ((exp + 1) << 23) & (0x7F800000);

  return (uf & ~0x7F800000) | exp;
}

12. floatFloat2Int

对尾数 M 部分的作用以及实现逻辑的理解有缺失，查阅资料后发现尾数的 M 实际隐藏了一个 1。严格来说尾数应当是 24 位， $2^0 + 2^{-1} + 2^{-2} + … + 2^{-23}$，其实际表示的范围为 $[1, 2 - 2^{-23}]$。（本质上 Normalized 和 Denormalized 是一致的，书上列了一张表显示二者之间是可以精确衔接的。

/*
 * 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) {
  // fraction should be cut off
  int exponent;
  unsigned bias = 127;
  unsigned sign = uf & (0x80000000); // 1 bit
  unsigned exp = uf & (0x7F800000);  // 8 bits
  unsigned frac = uf & (0x7FFFFF);   // 23 bits

  if (!(exp ^ 0x7F800000)) {
    return 0x80000000u;
  } // NaN or Infinity

  exp = exp >> 23; // get exponent value
  exponent = exp - bias;

  if (exponent > 31) {
    return 0x80000000u;
  }

  if (exponent < 0) {
    return 0;
  }

  // give frac the hiden main part
  frac |= 1 << 23;
  // fill the gap and move the binary point
  frac = (frac << 8) >> (31 - exponent);
  if ((!!sign)) {
    frac = ~frac + 1;
  }

  return frac;
}

另外在计算的时候需要考虑 bias 对的影响， 32 位机的 bias 依照公式应当为 $2^k - 1 = 127$，其中 k 为 exp 部分的位数。

由于 exponent 部分的范围是 $[-127, 128]$，小于零的 exponent 最终截断后的结果为 0，这是因为尾数 M 部分的范围是 $[1, 2 - 2^{23}]$，这是一个介于 1 和 2 之间的数，只要 $exponent <0, exponent \in \scriptstyle{Z}$ 则必有尾数小于 1 成立。而对于 exponent 大于 31 的情况则以溢出进行处理。

有一处报错值得注意，当时对于符号部分 sign 我是与 frac 做了 & 操作，这其实是对浮点数和整数关系的混淆。浮点数的 sign 是一种标志，说明当前的这个浮点数为负数，因而在转换过程中也应当将其作为符号处理。

ERROR: Test floatFloat2Int(-1082130432[0xbf800000]) failed
...
...Gives -2147483647[0x80000001]. Should be -1[0xffffffff]

13. floatPower2

/*
 * 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;
  int bias = 127;
  if (x > 128) {
    return 0x7F800000; // +INF(S = 0, exp = 0xFF)
  }

  if (x < -127) {
    return 0;
  }

  // exp = E + bias
  exp = x + bias;
  return exp << 23;
}

最后一题反倒是容易许多，需要留意 E 指数部分的范围，输入的 x 实际上就是这个指数，之后只需要将 exp 通过公式计算出来即可。

总结

# dlc checker
dlc:bits.c:149:bitXor: 8 operators
dlc:bits.c:158:tmin: 1 operators
dlc:bits.c:169:isTmax: 8 operators
dlc:bits.c:184:allOddBits: 9 operators
dlc:bits.c:194:negate: 2 operators
dlc:bits.c:210:isAsciiDigit: 12 operators
dlc:bits.c:224:conditional: 14 operators
dlc:bits.c:243:isLessOrEqual: 19 operators
dlc:bits.c:256:logicalNeg: 9 operators
dlc:bits.c:287:howManyBits: 36 operators
dlc:bits.c:316:floatScale2: 14 operators
dlc:bits.c:360:floatFloat2Int: 18 operators
dlc:bits.c:388:floatPower2: 5 operators

# btest checker
Score   Rating  Errors  Function
    1       0       bitXor
    1       0       tmin
    1       0       isTmax
    2       0       allOddBits
    2       0       negate
    3       0       isAsciiDigit
    3       0       conditional
    3       0       isLessOrEqual
    4       0       logicalNeg
    4       0       howManyBits
    4       0       floatScale2
    4       0       floatFloat2Int
    4       0       floatPower2
Total points: 36/36

整整做了一天半，还有一些题目参考了别人的思路，不然想破脑袋也难解决，在做 Lab 之前还以为这种基础性框架性的书给的 Lab 应该不算太难，结果是眼高手低。

在做 Lab 的时候也是对之前知识的回顾与查漏，像浮点数这块我理解的就不是特别透彻，结果就在做 Lab 时卡住了，基础知识掌握不牢后续遇到问题就是灾难。总的来说通过 datalab 我对整数，浮点数的概念有了比较清晰的理解和认识，也发现神奇的操作数能在限制极多的情况下也可以实现让人意想不到的功能。非常建议非 CS 科班但有代码工作需求的同学学习，即便到研究生阶段也有大用处。

我此前发现过一个非常有趣的网站也是关于 Bit 运算的，在这里分享一下， Bit Twiddling Hacks。 CSAPP 有时间还是得多翻翻~

Website

PREVIOUSu-boot 构建框架与启动分析

NEXTVSCodeVim 配置指南