CSAPP之DataLab详解

前言

本篇博客将会剖析 CSAPP - DataLab 各个习题的解题过程，加深对 int、unsigned、float 这几种数据类型的计算机表示方式的理解。

DataLab 中包含下表所示的 12 个习题，其中 9 个和整数有关，3个和单精度浮点数有关。

函数名	功能描述	分数	操作符
bitXor(x, y)	使用 & 和 ~ 实现异或操作	1	14
tmin()	补码的最小值	1	14
isTmax(x)	x 是否为补码的最大值	1	10
allOddBits(x)	x 的奇数位是否全为 1	2	12
negate(x)	不使用 - 计算 x 的相反数	2	5
isAsciDigit(x)	x 是否在 [0x30, 0x39] 区间内	3	15
conditional	实现条件运算符，x ? y : z	3	16
isLessOrEqual(x, y)	x 是否小于等于 y	3	24
logicalNeg(x)	不使用 ! 计算逻辑非	4	12
howManyBits(x)	表示 x 的最少补码位数	4	90
floatScale2(uf)	计算无符号数 uf 所表示的浮点数的 2 倍值	4	30
floatFloat2Int(uf)	将无符号数 uf 所表示的浮点数转为整数	4	30
floatPower2(x)	计算 \(2^x\)	4	30

解题

整数题目

整数题目对代码的要求比较严格，不允许使用超过 0xFF 的整数字面量，也不能使用 if、while 等关键字，只能使用最基本的加法和位操作实现所需功能。

bitXor(x, y)

题目要求只使用 ~ 和 & 实现异或，我们只需用德摩根定律对异或的布尔表达式做一下变换即可：

\[x\oplus y = \bar{x}y+x\bar{y} = \overline{\overline{\bar{x}y} \cdot \overline{x\bar{y}} }\]

有了上面的式子之后就很简单了，代码如下：

/* * 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));}

tmin()

对于 4 个字节的有符号数，\(T_{min}=-2^{32-1}=0b10\cdots0\)，只需将 1 左移 31 位即可得到。

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

isTmax(x)

对于 4 个字节的有符号数，\(T_{max}=2^{32-1}-1=0b01\cdots1\)，题目不允许使用移位操作，所以有必要利用一下 \(T_{max}\) 的性质来解题：

\[T_{max}=0b01\cdots1=\sim 0b10\dots0=\sim T_{min}\\-T_{min}=\sim T_{min}+1=T_{min}\]

也就是说，如果 x 是 \(T_{max}\) ，只需对它按位取反，再判断它满不满足相反数即自身这个性质即可。但是除了 \(T_{min}\) 之外，0（\(\sim-1=\sim0b1\cdots1=0\)） 也满足相反数即自身这一特点，所以需要将其排除。代码如下：

/* * 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) {    int y = ~x;    int y_ = ~y + 1;    int isZero = !(y ^ 0);    return !isZero & !(y ^ y_);}

allOddBits(x)

对于所有奇数位都是 1 的整数，一定满足下式：

\[x = 0b1x_{30}1x_{28}\cdots1x_{0}, 其中 x_{2i}\in \{0, 1\}\\x\ |\ (x \gg 1)=0b11\cdots 1\]

将 x 按位或右移 1 位的 x 一定可以得到每位都是 1 的整数，也就是 -1。但是有一个例外，当 x 为 0b1101（这里自取 4 位，方便理解）时，虽然他没有满足所有奇数位都是 1 的要求，但是仍然有 \(x\ |\ x\gg1=1101 | 1110=1111\)，所以我们有必要将 x 中的 4 的整数倍位清 0，即 \(x_{4i}=0\)，由于这些都是偶数位，所以不必有任何的顾虑。

只需将 \(x\& 0xEEEEEEEE\) 就能做到上述的清零操作，整数实验不允许使用大于 255 即 0xFF 的字面量，所以我们只能通过移位来构造 0xEEEEEEEE，代码如下：

/* * 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 = 0xEE + (0xEE << 8);    mask = mask + (mask << 16);    int y = x & mask;    int z = y | (y >> 1);    return !(~z ^ 0);}

negate(x)

要计算相反数，只需按位取反之后再加 1 即可。

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

isAsciiDigit(x)

这题要判断 x 是否为 Ascii 码 0~9 中的某一个，即要求 \(0x30\le x \le 0x39\)，可以分两步实现判断。

首先判断低 4 位 \(x_3x_2x_1x_0\) 是否在 0~9 范围内。当 \(x_3\) 为 0 时，低 4 位在 0~7 范围内；当 \(x_3\) 为 1 时，只要 \(x_2\) 和 \(x_1\) 为 0，低四位就在 8~9 范围内。由此得到的布尔表达式为：

\[A=\bar{x}_3+x_3\bar{x}_2 \bar{x}_1\]

接着判断 \(x_7x_6x_5x_4\) 是否为 3，只要将 x 右移 4 位之后异或 3 再逻辑取反就能得到判断结果。

/* * 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) {    // 判断低 4 位是否在 0~9 范围内    int is0To9 = !((x & 8) ^ 0) + !((x & 14) ^ 8);    // 判断高 4 位是否为 3    int isThree = !((x >> 4) ^ 3);    return is0To9 & isThree;}

conditional(x, y)

要实现 w = x : y ? z，只需实现函数 \(f(x, y, z)=z\ \&\ g(x)+y\ \& \ \sim g(x)\)，其中 \(g(x)\) 满足下式：

\[g(x)=\left\{\begin{aligned}0b11\cdots 1 \quad & x=0 \\0b00\cdots 0 \quad & x\neq 0\end{aligned}\right.\]

要实现 \(g(x)\)，只需先将 x 异或 0，如果 x 为 0，结果就是 0，否则为非 0 数，接着再逻辑取反，得到的数不是 1 就是 0，再按位取反并加 1，就能得到 \(g(x)\)。代码如下：

/* * 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 ^ 0)) + 1;    return (y & ~mask) + (z & mask);}

isLessOrEqual(x, y)

比较两个数的大小，首先应该比较符号位。如果 x 为正，y 为负，直接返回 0；如果如果 x 为负，y 为正，直接返回 1。

如果 x 和 y 同号，则判断 \(z=x-y\le0\) 是否成立。由于题目不允许使用减号操作符，所以换成判断 \(z=x+(-y)=x+(\sim y+1)\le 0\)。只要 z 的符号位为 1，x 就小于 y，如果 z 为 0，说明 x 等于 y。

/* * 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 signX = (x >> 31) & 1;    int signY = (y >> 31) & 1;    // 大小比较    int z = x + (~y + 1);    int isLe = !((z & (1 << 31)) ^ (1 << 31)) | !(z ^ 0);    return (!(~signX & signY)) & ((signX & ~signY) | isLe);}

logicalNeg(x)

逻辑取反，x 非 0 返回 0，x 为 0 返回 1。在实现 isTmax(x) 时，我们说过 0 满足 \(-0=0\)，即 \(0\ |\ (\sim0+1)\) 得到的结果还是 0。而其他非 0 数按位或自己的相反数，符号位一定会是 1。由此可以写出逻辑非的代码：

/* * 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) {    return ((x | (~x + 1)) >> 31) + 1;}

howManyBits(x)

题目要求计算出表示 x 的最少补码位数，比如：

• \(0=0b0\)，只需 1 位即可表示
• \(-1=0b1\)，也只需 1 位来表示
• \(1 = 0b01 \in[-2, 1]\)，需要 2 位来表示
• \(-2=0b10\in [-2, 1]\)，需要 2 位来表示
• \(2=0b010\in [-4, 3]\)，需要 3 位来表示
• \(3=0b011\in [-4, 3]\)，需要 3 位来表示
• \(-3=0b101\in[-4, 3]\)，需要 3 位来表示

观察上面的二进制数和他们所需的位数，可以发现如果 x 为正数，从左到右扫描，第一个 1 出现的位置 +1 就是所需位数。如果 x 为负数，将其按位取反转换为正数后再进行相同判断即可。

我们可以采用二分法来从左到右寻找第一个 1 出现的位置。首先去高 16 位看看有没有 1 出现，如果有就把 x 右移 16 位后的值赋给 x，再去移位后 x 的低 16 位二分查找。如果高 16 位没有出现 1，就在低 16 位二分查找。

int howManyBits(int x) {    int sign = x >> 31;    // 将 x 转换为正数，这样只要判断最高位 1 出现的位置即可    x = (sign & ~x) | (~sign & x);    // 判断高16位是否存在 1，如果有就右移 x    int b16 = (!!(x >> 16)) << 4;    x = x >> b16;    // 判断高 8 位是否存在 1，如果有就右移 x    int b8 = (!!(x >> 8)) << 3;    x = x >> b8;    // 判断高 4 位是否存在 1，如果有就右移 x    int b4 = (!!(x >> 4)) << 2;    x = x >> b4;    // 判断高 2 位是否存在 1，如果有就右移 x    int b2 = (!!(x >> 2)) << 1;    x = x >> b2;    int b1 = !!(x >> 1);    int b0 = x >> b1;    return b16 + b8 + b4 + b2 + b1 + b0 + 1;}

浮点数题目

浮点数题目对代码的要求没有整数题目那么严格，可以在代码里面使用超过 0xFF 的整数字面量，可以使用 if、while 关键词，还能使用 ==、>= 等逻辑运算符。

floatScale2(uf)

题目要求将无符号数 uf 表示的单精度浮点数 f 乘以 2，可以分为两种情况：

• 如果 f 为非规格化数，即 exp 字段为 0，此时 f 小于 1，只需将 uf 算术左移即可
• 如果 f 为规格化数，即 exp 字段不为 0，乘以 2 只需将 exp+1 即可，但是 +1 之后可能使得 exp 变为 0xFF，即发生了溢出，这时候需要返回 \(+\infty\) 或者 \(-\infty\)

代码如下所示：

/* * 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 exp = (uf & 0x7f800000) >> 23;    if (exp == 255) {        return uf;    }    // 取出符号位    unsigned sign = uf & 0x80000000;    // 非规格化数，直接左移扩大两倍    if (exp == 0) {        return uf << 1 | sign;    }    // 溢出    if (++exp == 255) {        return sign | 0x7f800000;    }    return exp << 23 | (uf & 0x807fffff);}

floatFloat2Int(uf)

题目要求将浮点数 f 强转为整数，根据 \(E=exp-Bias\) 的值可以分为几种情况：

• 如果 \(E\) 小于 0，说明 f 要么是非规格化数（\(exp\) 为 0，这里没有使用 \(1-Bias\) 因为只看 \(E\) 的符号），要么是一个小于 2 的数乘上了 \(1/2^n\) ，两种情况下 f 的绝对值都小于 1，只需返回 0 即可
• 如果 \(E\) 大于 31，说明 \(|\pm 1.XX\cdots X|\) 至少变成原来的 \(2^{32}\) 倍，由于整数只有 4 个字节，这时候发生了溢出，返回 0x80000000
• 如果 \(23\lt E\lt 31\)，说明 \(|\pm 1XX\cdots X|\) （注意这里没有小数点，所以需要大于 23）需要左移（扩大）才能表示浮点数的值 ，左移的过程中可能改变符号为负，说明发生了溢出，需要返回 0x80000000
• 如果 \(0\le E\le 23\)，说明 \(|\pm 1XX\cdots X|\) 需要右移（缩小）才能表示浮点数的值

代码如下所示：

/* * 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) {    // 计算阶码    unsigned exp = (uf & 0x7f800000) >> 23;    int e = exp - 127;    // 0或小数直接返回 0    if (e < 0) {        return 0;    }    // NaN 或者 无穷大    if (e > 31) {        return 0x80000000;    }    // 尾数    int frac = (uf & 0x7fffff) | 0x800000;    // 移动小数点    if (e > 23) {        frac <<= (e - 23);    } else {        frac >>= (23 - e);    }    // 符号位不变    if (!((uf >> 31) ^ (frac >> 31))) {        return frac;    }    // 符号位变化，且当前符号为负，说明溢出    if (frac >> 31) {        return 0x80000000;    }    // 符号变化，返回补码    return ~frac + 1;}

floatPower2(x)

这题比较简单，要求计算 \(2^x\) ，只要将 exp 加上 x 即可。因为 x 变化范围太大，可能导致 exp 小于 0 或者大于 255，这时候就要返回 0 或者无穷大。

/* * 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 = 127 + x;    // 溢出    if (exp >= 255) {        return 0x7f800000u;    }    // 太小以至于无法用非规格化数来表示    if (exp < 0) {        return 0;    }    return exp << 23;}

总结

做完习题之后收获还是挺大的，做题的过程也产生了一些想法：

• 看书还是挺无聊的，配合 B 站的网课食用更香，而且看 CMU 网课的感觉和看国内慕课的感觉完全不一样，看慕课的时候只想着开倍数刷完了事，而看 CMU 网课的时候就觉得大牛慢慢悠悠的节奏很舒服，可以看得很投入
• int 和 unsigned 的底层二进制数是一样的，只是看待这个二进制数的方式不同，只要记住数轴即可

以上~~