CSAPP Datalab Solution

使用 C 语言，在限定条件下，在 bits.c 文件中实现下列函数：

具体的限制条件参考 Self-Study Handout，一个简略的限制条件说明放在了结尾

下表中的 Max Ops Allowed 字段表示“最多可以使用的操作符个数”

Func Name	Description	Max Ops Allowed
bitXor(x,y)	仅用 & 和 ~ 实现 x xor y	14
tmin()	返回最小的二进制补码整数	4
isTmax(x)	判断 x 是否为最大的二进制补码整数	10
allOddBits(x)	判断 x 的所有奇数位是否均为 1	12
negate(x)	不使用 - 运算符返回 -x	5
isAsciiDigit(x)	判断 x 是否为 ASCII 数字（0x30 ≤ x ≤ 0x39）	15
conditional(x,y,z)	实现 x ? y : z 的功能	16
isLessOrEqual(x, y)	判断 x 是否小于等于 y	24
logicalNeg(x)	不使用 ! 运算符实现 !x	12
howManyBits(x)	返回表示 x 所需的最小位数	90
floatScale2(uf)	返回与表达式 2 * f 等价的二进制位表示	30
floatFloat2Int(uf)	将浮点数转换为整数	30
floatPower2(x)	返回与表达式 2.0 ^ x 等价的二进制位表示	30

---

Solution

1. 仅用 & 和 ~ 实现 x ^ y

对 xor 式子进行变换，第一步拆开 xor 表达式为和或非形式，第二步使用德摩根律消去 | 运算

--> x ^ y = ~( (~ (~x & y)) & (~ (x & ~y)) )

code:

int bitXor(int x, int y) {
    return ~( (~ (~x & y)) & (~ (x & ~y)) );
}

2. 返回最小的二进制补码整数

要求中提到：整数常量只能设置在 0 到 255（ 0xff ），不允许使用更大的常量（如 0xffffffff）

我们知道最小的二进制补码整数是 10000000 00000000 00000000 00000000 （题设使用 32 位二进制补码表示整数），可以选择将 10000000 左移 24 位实现

code:

int tmin(void) {
    return 0x80 << 24;
}

3. 判断 x 是否为最大的二进制补码整数

不能使用控制函数，所以不能 if

我们知道最大的二进制补码整数是 01111111 11111111 11111111 11111111 ，这个数有一个特性： +1 操作与取反操作得到相同的值。

总共有两个数符合这样的特性： Tmax 与 -1 ，所以我们先通过 !( (x+1) ^ (~x) ) 排除掉其他值，再通过 !(!(~x)) 操作排除 -1 这个值（只有 -1 取反后为 0）

当然，直接构造出 0x80000000，利用异或性质得到答案是更加简洁的选择，但是第一个函数不依赖 int 在不同环境下的位数限制，具有更好的可移植性；而第二个函数的 0x80<<24 操作只针对于 32 位 int （并且这一题禁止了移位操作，所以后者得不到分）

! 的作用

! 可以将所有非零数统一设置为 0，在没有 if == 操作的情况下，这很实用

判断 a,b 是否相等的一个简单操作是： !(a^b) ，相等值为 1，否则值为 0

code:

int isTmax(int x) {
    return !( (x+1) ^ (~x) ) & !(!(~x));
}

4. 判断 x 的所有奇数位是否均为 1

也就是判断一个数和掩码 01010101 01010101 01010101 01010101 的按位或结果是否为 0xffffffff ，如果是，取反后就能得到 0，利用 ! 操作就能解答

code:

int allOddBits(int x) {
    int y = 0x55 + (0x55 << 8);
    int z = y + (y << 16);
    return !( ~(x | z) );
}

5. 不使用 - 运算符返回 -x

对于补码数，取负操作等价为 “按位取反 + 1” ，据此给出解答

取负运算 - 和取反运算 ~

取负操作 -x 的定义是使 x+(-x) 在模 $2^n$ 运算下为 0，$n$ 是数据长度

不难得到 $x+(\sim x + 1) = 2^n \equiv 0 \pmod {2^n}$

code:

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

6. 判断 x 是否为 ASCII 数字（0x30 ≤ x ≤ 0x39）

首先得从 0x30 ~ 0x39 这几个二进制数的性质入手，这些数的二进制都满足右八位为 0011xxxx，且 xxxx 部分只能对应十六进制 0~9 （具体来说是满足 0xxx（0~7）或者 100x（8~9）格式的值）

总结一下就是这个数 x 必须能与 00110xxx 与 0011100x 中的某一项匹配。对于匹配 00110xxx，我们可以先将 x 右移三位，然后与 00110 进行比较（ 0011100x 同理）

code:

int isAsciiDigit(int x) {
    return !( (x >> 3) ^ (0x06) ) | !( (x >> 1) ^ (0x1c) );
}

7. 实现三目运算符 x ? y : z 的功能

等价于 ：if(x != 0) {return y;} else {return z;}

注意到对任意 32 位整数 a， 0 & a == 0 且 0xffffffff & a == a ，我希望构造一个函数 f(x) ，满足 x==0 时 f(x) == 0；x != 0 时 f(x) == 0xffffffff ，这样的话我就可以通过这个函数构造三目运算符，大致原理是：

--> return f(x) & y | ~f(x) & z

考虑 !x 操作只会将 x 变为 0 或 1 ，而这两个数减去一恰好对应 0xffffffff 与 0 ，这就解决了构造函数的问题：f(x) = (!x) - 1 （题目要求只能用加号，所以这里还需要构造 -1 ）

code:

int conditional(int x, int y, int z) {
    int c = !x + (~0);                  // 也可以写成 ~(!!x) + 1
    return (c & y) | (~c & z);
}

8. 判断 x 是否小于等于 y

如果 x <= y 返回 1，否则返回 0

容易发现： x <= y 有两种情况：x 负 y 非负；或者 x y 同正负且满足 y-x 符号位为 0

--> return ( (x,y 同号) & !((y-x) >> 31) ) | (x负且y非负)

为什么要加上对 x y 符号的讨论？

防止溢出情况改变了符号位

code:

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

9. 不使用 ! 运算符实现 !x

! 的运算解释：如果 x 非零，则 !x = 0，否则 x == 0 → !x = 1

注意到对于任意非零数 x ，x 与 -x 总有一个符号位为 1，而 x == 0 时 x == -x == 0，符号位为 0 ，根据这个符号位差异就可以写出函数

C 语言对于有符号数采用算术右移，所以 x != 0 时右移 31 位结果为 -1

code:

int logicalNeg(int x) {
    return ((x | (~x + 1)) >> 31) + 1;
}

10. 返回能完整表示 x 所需的最小位数

/*  Examples: howManyBits(12) = 5                   (0 1100)
 *            howManyBits(298) = 10                 (0 100101010)
 *            howManyBits(-5) = 4                   (1 011)
 *            howManyBits(0)  = 1                   (0)
 *            howManyBits(-1) = 1                   (1)
 *            howManyBits(0x80000000) = 32          (1 + 31*0)
 */

int 部分题目的最难题，甚至给了最多 90 步的限制，是场恶战

首先 x 的值为 0 和 -1 都是特殊情况（只需要符号位表示），先留意一下

对于一般情况，如果 x 是正数，那么关键目的是要尝试找到最高有效位（该位为 1 ，其左侧全为 0 ），最小位数 = 最高有效位 + 一位符号位

如果 x 是负数，不能直接用上面的方案找最高有效位，因为补码额外有一个值为 1 的符号位，使得最终结果比正确结果多出一，因此必须先取绝对值化。这里可以选择对 x 取反，~x 和 x 的所需最小位数是相同的（比如 1011 取反后为 0100 ，所需最小位数都是 4 位），注意 -1 是特例。

如何判断一个数是不是负数？检查符号位：

int sign = x >> 31;
x = (sign & ~x) | (~sign & x);  // 这里是三目运算符的一个运用

统一了 x 的正负性之后，符号位不再影响最高有效位的寻找。这里考虑二分查找找到最高有效位，下面是伪代码：

int Max = 0;                    // 记录最高有效位的数值
if (x 的高 16 位全为零){
    x = x << 16 >> 16;          // 只保留低 16 位，因为高 16 位已经没有信息提供了
}
else {                          // 也就是说最高有效位出现在高 16 位中
    x = x >> 16;                // 把高 16 位当作低 16 位储存
    Max = Max + 16;             // 后 16 位都贡献了最高有效位
}

if (x 的高 8 位全为零){           // 对剩下的部分继续二分寻找
    x = x << 8 >> 8;
}
else {
    x = x >> 8;
    Max = Max + 8;
}

// 此处省略一部分查找过程

if (x 的高 1 位为零) {
    x = x << 1 >> 1;
}
else {
    x = x >> 1;
    Max = Max + 1;
}

Max = Max + (x != 0);           // 最后计算剩下的一位的贡献

现在我们需要考虑如何实现上面的伪代码，我们聚焦于这一部分内容的实现：

if (x 的高 16 位全为零){
    x = x << 16 >> 16;          // 只保留低 16 位，因为高 16 位已经没有信息提供了
}
else {                          // 也就是说最高有效位出现在高 16 位中
    x = x >> 16;
    Max = Max + 16;             // 后 16 位都贡献了最高有效位
}

给出这一部分的 C 语言实现：

int check = !!(x & 0xffff0000);     // 高 16 位全零时值为 0，否则值为 1；
Max = Max + (check << 4);           // 将 0 1 映射到了 0 16，这恰好满足对 Max 的增加情况
x = x >> (check << 4);              // 如果高 16 位不为 0，那就把高 16 位移到低 16 位的位置，否则不改变 x 的值

为什么要这么移动 x ？

这几次查找用到的掩码值分别为 0xffff0000 0x0000ff00 0x000000f0 0b1100 0b10 ，你可以从掩码的构造发现移位的目的

结合最开始提到的 x 的值为 0 和 -1 的特殊情况，可以给出代码

code:

int howManyBits(int x) {
    int sign = x >> 31;                 // 算术右移
    int check = 0;                      // dlc 程序要求变量必须在最开始声明
    int Max = 0;
    x = (sign & ~x) | (~sign & x);

    check = !!(x & ((0xff + (0xff << 8)) << 16) );  // 题目限制常量不大于0xff，需要额外构造
    Max = Max | (check << 4);           // 这里用 | 代替了 +，因为每次 Max 的变化都只涉及单一数位
    x = x >> (check << 4);
    check = !!(x & (0xff << 8) );
    Max = Max | (check << 3);
    x = x >> (check << 3);
    check = !!(x & 0xf0);
    Max = Max | (check << 2);
    x = x >> (check << 2);
    check = !!(x & 0xc);
    Max = Max | (check << 1);
    x = x >> (check << 1);
    check = !!(x & 0x2);
    Max = Max | check;
    x = x >> check;
    Max = Max + !!(x | 0);

    return (!x & 1) | (~!x & Max+1);    // 对 x == -1 进行了特判（发现 x == 0 不需要特判） 
}

接下来的三道题为浮点数题目，放开了 if while 控制语句，|| && == 的使用

11. 返回与表达式 2 * f 等价的二进制位表示

把 f 理解为单精度浮点数，对于 NaN Inf 直接输出原数，对于规格化数将指数部分加 1，对于非规格化数将尾数部分左移一位。需要注意的是，对于非规格化数的底数左移，可能会使其变成规格化数，实际上直接将尾数部分左移即可，没有特殊影响

code:

unsigned floatScale2(unsigned uf) {
    // 提取指数位
    unsigned exp = (uf >> 23) & 0xff;
    // 特殊值
    if(exp == 0xff){
        return uf;
    }
    // 非规格化数
    if(exp == 0){
        return (uf & 0x80000000) | ((uf & 0x007fffff) << 1);
    }
    // 规格化数
    {
        return (uf & 0x807fffff) | ((uf & 0x7f800000) + 0x00800000);
    }
}

12. 将浮点数 f 转换为整数

对于 NaN Inf 输出 0x80000000u ，对于其他 f，进行强制类型转换为 int 操作

对于非规格化数，其表示范围非常小（指数 E = -126），所以转换为 int 后一定近似为 0

对于规格化数，指数 E = exp - 127 ，当 E >= 31 时，这个数一定超过了 int 范围，输出 0x80000000u ；当 E < 0 时， |f| < 1，考虑到强制类型转换是向零舍入（也就是抹去小数点），转换为 int 后一定近似为 0 （这一情况可以与非规格化数的情况合并处理）

对于规格化数，指数 E 在 [0,30] 之间，此时我们可以开始构造整数了：

$$ (-1)^S \times 1.xxx \times 2^E $$

考虑非负数情况 S == 0（负数需要额外取反加一），先取尾数部分 frac = uf & 0x007fffff; ，规格化补上前导 1： frac = frac | 0x00800000 。得到完整的规格化尾数之后，根据 E 的值进行位移：以 23 为位移分界线（尾数长度，也就是说在不移位的情况下，此时的 frac 表示的就是指数为 23 的结果），指数超过 23 说明需要左移，低于 23 说明需要右移（同时起到向零舍入的作用）

最终加上符号位判断 sign ? -frac : frac ，完成实现

code:

int floatFloat2Int(unsigned uf) {
    unsigned exp = (uf >> 23) & 0xff;
    unsigned frac = uf & 0x007fffff;
    unsigned sign = uf >> 31;
    if(exp > 157){
        return 0x80000000u;
    }
    if(exp < 127){
        return 0;
    }
    frac = frac | 0x00800000;
    if(exp > 150){
        frac = frac << (exp - 150);
    }
    else {
        frac = frac >> (150 - exp);
    }

    if (sign){
        return ~frac + 1;
    }
    else {
        return frac;
    }
}

13. 返回与表达式 2.0 ^ x 等价的二进制位表示

“如果结果太小无法用非规格化数表示，则返回 0。如果结果太大，则返回 +INF ”

最小的非规格化数（正数）是 0x1 ，对应的值为 $2^{-23} \times 2^{-126} = 2 ^{-149}$，所以 x < -149 时返回 0 ；非规格化数的 x 的取值范围是 [-149, -127] ；规格化数的取值范围是 [-126, 127] ，x > 127 时返回 +INF = 0x7F800000

非规格化数采用 1 << (x + 149) 构造；规格化数采用 (x + 127) << 23 构造

code:

unsigned floatPower2(int x) {
    if(x < -149){
            return 0;
        }
    if(x > 127){
        return 0x7f800000;
    }
    if(x > -127){
        return (x + 127) << 23;
    }
    {
        return 1 << (x + 149);
    }
}

---

附： driver.pl 评测结果

Correctness Results     Perf Results
Points  Rating  Errors  Points  Ops     Puzzle
1       1       0       2       8       bitXor
1       1       0       2       1       tmin
1       1       0       2       8       isTmax
2       2       0       2       7       allOddBits
2       2       0       2       2       negate
3       3       0       2       7       isAsciiDigit
3       3       0       2       7       conditional
3       3       0       2       14      isLessOrEqual
4       4       0       2       5       logicalNeg
4       4       0       2       54      howManyBits
4       4       0       2       12      floatScale2
4       4       0       2       14      floatFloat2Int
4       4       0       2       9       floatPower2

Score = 62/62 [36/36 Corr + 26/26 Perf] (148 total operators)

附：Datalab 题目限制

• 整数编码规则（前十题）

替换每个函数中的 return 语句，用一行或多行 C 代码实现该函数。

每个表达式 Expr 只能包含以下内容：（比如 int var1 = Expr1; 中的 Expr1 就是一个表达式）

1. 整数常量：0 到 255（0xff），不允许使用更大的常量（如 0xffffffff）。
2. 函数参数和局部变量：不能使用全局变量。
3. 一元整数运算：!（逻辑非）、~（按位取反）。

4. 二元整数运算：&（按位与）、^（按位异或）、|（按位或）、+（加法）、<<（左移）、>>（右移）。

5. 每个 Expr 可以包含多个运算符，不限制每行只能有一个运算符。

不能使用的：

1. 控制结构：如 if、do、while、for、switch 等。
2. 宏定义：不能定义或使用宏。
3. 额外函数：不能在本文件中定义其他函数。
4. 函数调用：不能调用任何函数。
5. 其他运算符：如 &&、||、-、?:（三元运算符）。
6. 类型转换：不能使用任何形式的强制类型转换。
7. 其他数据类型：只能使用 int，不能使用数组、结构体或联合体

机器假设

1. 整数表示：使用 32 位二进制补码表示整数。
2. 右移行为：算术右移（高位补符号位）。
3. 移位异常：如果移位量 < 0 或 > 31，行为是未定义的。

一个正确的函数实现例子：

// 计算 2^x+4 的值
int pow2plus4(int x) {
    /* 利用移位计算 2 的幂 */
    int result = (1 << x);
    result += 4;
    return result;
    // 也可以直接写：return (1 << x) + 4;
}

• 浮点数编码规则（后三题）

对于需要实现浮点数操作的题目，编码规则相对宽松。允许使用：

• 循环和条件控制（如 if、while 等）。
• int 和 unsigned 数据类型。
• 任意整数和无符号常量。
• 任何算术、逻辑或比较运算符（作用于 int 或 unsigned 数据）。

明确禁止的内容

1. 宏定义：不能定义或使用宏。
2. 额外函数：不能在本文件中定义其他函数。
3. 函数调用：不能调用任何函数。
4. 类型转换：不能使用任何形式的强制类型转换。
5. 其他数据类型：只能使用 int 或 unsigned，不能使用数组、结构体或联合体。
6. 浮点数相关操作：
7. 不能使用浮点数据类型（如 float、double）。
8. 不能使用浮点运算符（如 +、* 等作用于浮点数）。
9. 不能使用浮点常量（如 3.14、0.5f）。

细化到每一题的注意事项可以在 bits.c 的每一题的注释中查看

2025-10-232025-11-21