本篇文章是 CS:APP（《深入理解计算机系统》）第三个版本 Lab 1: Data Lab 的完整题解，涵盖整数位运算与浮点数运算两部分，包含每道题目的思路推导与代码实现。

---

Lab1代码已更新至github

环境配置

这个 Lab 需要在 Linux 环境下完成，推荐以下三种方案：

1. WSL2（Windows 自带，推荐）
2. 虚拟机（如 VMware / VirtualBox 安装 Ubuntu）
3. 云服务器（如阿里云、腾讯云轻量应用服务器）

在新的环境下学习时, 往往配置环境就要折腾半天, 还没开始学习就先力竭了，因此这里提供一份现成的 WSL 配置指南：

WSL 环境配置教程

如果你觉得手动配置过于繁琐，也可以借助 Claude Code 的免费额度来协助配置 WSL 环境。

下载并部署实验文件

在 CSAPP 官方 Lab 页面 下载 datalab-handout.tar，将其解压到 Linux 环境中：

# 启动 WSL
wsl

# 将压缩包从 Windows 文件系统复制到 Linux 中
cp /mnt/c/Users/<你的Windows用户名>/Downloads/datalab-handout.tar ~

# 进入根目录并解压
cd ~
tar -xvf datalab-handout.tar

# 进入 Lab 目录
cd datalab-handout

常见编译错误

如果执行 make 时遇到以下错误：

26 | #include <bits/libc-header-start.h>
   | ^~~~~~~~~~~~~~~~~~~~~~~~~~
   compilation terminated.
make: *** [Makefile:11: btest] Error 1

这是因为缺少 32 位编译支持，安装 gcc-multilib 即可：

sudo apt-get install gcc-multilib

本 Lab 还需要 make 工具，如果尚未安装：

sudo apt update
sudo apt install -y build-essential

# 验证安装
make --version

---

Lab 概览

Data Lab 由 整数位运算（10 题）和 浮点数运算（3 题）两部分组成，共 13 个问题。每道题都限制了可使用的运算符集合和最大操作次数，要求你在这些约束下用纯位运算实现目标功能。

整数位运算

题目	运算符限制	描述	难度	最大操作数
bitXor(x, y)	~ &	计算 x ^ y	1	14
tmin(void)	! ~ & ^ \| + << >>	返回 32 位有符号整数的最小值	1	4
isTmax(x)	! ~ & ^ \| +	判断 x 是否为 32 位有符号整数的最大值	1	10
allOddBits(x)	! ~ & ^ \| + << >>	判断 x 的所有奇数位是否全为 1	2	12
negate(x)	! ~ & ^ \| + << >>	返回 -x	2	5
isAsciiDigit(x)	! ~ & ^ \| + << >>	判断 x 是否在 [0x30, 0x39] 范围内	3	15
conditional(x, y, z)	! ~ & ^ \| + << >>	用位运算实现三目运算符 x ? y : z	3	16
isLessOrEqual(x, y)	! ~ & ^ \| + << >>	判断 x <= y	3	24
logicalNeg(x)	~ & ^ \| + << >>	不使用 ! 实现逻辑非	4	12
howManyBits(x)	! ~ & ^ \| + << >>	返回用补码表示 x 所需的最少位数	4	90

浮点数运算

题目	运算符限制	描述	难度	最大操作数
floatScale2(uf)	无限制（可用 if / while）	返回 uf * 2.0 的位级表示	4	30
floatFloat2Int(uf)	无限制（可用 if / while）	将浮点数强转为 int 的位级表示	4	30
floatPower2(x)	无限制（可用 if / while）	返回 2.0^x 的位级表示	4	30

---

编译 & 测评工具

基本流程

# 每次修改代码后重新编译
make

# 清除编译产物
make clean

# 运行全部测评
./btest

# 测评指定函数
./btest -f <函数名>

# 用自定义数据测评指定函数
./btest -f <函数名> <参数1> <参数2> ...

辅助工具

dlc — 检查运算符合规性：

# 检查是否使用了非法运算符
./dlc bits.c

# 打印每道题实际使用的操作符数量
./dlc -e bits.c

bddcheck — 穷举所有可能输入进行验证：

./bddcheck/check.pl

driver.pl — 整体评分脚本：

./driver.pl

ishow — 查看整数的位级表示：

./ishow 1

# 输出: Hex = 0x00000001, Signed = 1, Unsigned = 1.

fshow — 查看浮点数的位级表示：

./fshow 1.2

# 输出:
# Floating point value 1.200000048
# Bit Representation 0x3f99999a, sign = 0, exponent = 0x7f, fraction = 0x19999a
# Normalized. +1.2000000477 X 2^(0)

---

题目详解

前置知识

1. !! ：!!x 能将任意非零值置为为 1，零值置为 0。而 !x 会在规约的同时取反。
2. x & 0x00000000 将 x 清零，x & 0xFFFFFFFF 保留 x 本身。
3. 判断相等：(x ^ y) == 0 当且仅当 x == y。
4. 相反数公式：-x = ~x + 1。
5. 逻辑组合：多个布尔判断用 |（或）连接得到"任一为真即为真"；用 &（与）连接得到"全部为真才为真"。

---

bitXor

• 描述：仅使用 ~ 和 & 实现异或运算 x ^ y
• 运算符限制：~ &
• 最大操作数：14
• 难度：1

推导：

由布尔代数可知：

$$x\oplus y=(x\mid y)\&\sim (x\&y)$$

我们已知 & 和 ~，但缺少 |。根据摩根定律：

$$\sim (x\mid y)=(\sim x)\&(\sim y)$$

两边同时取反，得到 | 的等价表达：

$$x\mid y=\sim ((\sim x)\&(\sim y))$$

代入原式即可。

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

---

tmin

• 描述：返回 32 位补码能表示的最小整数（$T_{min}$）
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：4
• 难度：1

推导：

补码的最小值是负数。对于同符号位的数，去掉符号位后剩余部分越大，数值越大。因此最小负数就是符号位为 1、其余位全 0，即 0x80000000，等价于 $2^{31}$。

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

---

isTmax

• 描述：若 x 是 32 位补码能表示的最大整数（$T_{max}$），则返回 1；否则返回 0
• 运算符限制：! ~ & ^ | +
• 最大操作数：10
• 难度：1

推导：

最大补码为 0x7FFFFFFF。既然要基于它进行判断, 那么一定要找到它与其他数的不同点

观察发现：只有 Tmax 和 -1 满足 ~(x + 1) == x。

	Tmax	-1
原值	0111...1111	1111...1111
+1	1000...0000	(1)0000...0000（高位溢出）
~ 后	0111...1111	1111...1111

需要排除 -1：注意到只有 -1 在 +1 后会变成 0，用 !!(x + 1) 即可区分。

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

---

allOddBits

• 描述：若 x 的所有奇数位（从 0 开始编号）全为 1，返回 1；否则返回 0
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：12
• 难度：2

推导：

0xAAAAAAAA 的二进制是 10101010...，恰好所有奇数位为 1、所有偶数位为 0。

思路分两步：

1. 清除偶数位：x & 0xAAAAAAAA 将 x 的偶数位全部置 0。
2. 利用异或判断相等：若 x 的奇数位全为 1，则 (x & mask) ^ mask == 0；否则结果非 0。最后取 ! 即可。

注意：题目限定 x 为 8 位以内的值（即 [0, 255]），因此不能直接使用 0xAAAAAAAA。需要从 0xAA 出发，通过左移倍增：

int allOddBits(int x) {
    int mask = 0xAA;
    mask = mask | (mask << 8);
    mask = mask | (mask << 16);
    return !((mask & x) ^ mask);
}

---

negate

• 描述：返回 -x
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：5
• 难度：2

推导：

直接套用补码的相反数公式：-x = ~x + 1。

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

---

isAsciiDigit

• 描述：若 0x30 <= x <= 0x39（即 ASCII 字符 '0' 到 '9'），返回 1；否则返回 0
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：15
• 难度：3

推导：

需要同时满足两个条件：x >= 0x30 且 x <= 0x39。

判断 x >= y 可以转化为判断 x + (-y) 的符号位——若结果非负（符号位为 0），则 x >= y。

x >= 0x30 成立？	x <= 0x39 成立？	最终结果
1	1	1
1	0	0
0	0	0
0	0	0

容易发现上表恰好对应 逻辑与 关系。

int isAsciiDigit(int x) {
    int ver1 = x + (~0x30) + 1;   // x - 0x30
    int ver2 = 0x39 + (~x) + 1;   // 0x39 - x

    ver1 >>= 31;   // 符号位
    ver2 >>= 31;

    return !ver1 & !ver2 & !(x >> 31); 
}

---

conditional

• 描述：用纯位运算实现三目运算符 x ? y : z
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：16
• 难度：3

推导：

因为要把 x 转换为 0/1 值 flag , 所以用 !! 操作

可以用 ~flag + 1来将 1 变为 0xFFFFFFFF, 0 变为 0x00000000

这样就可以在 x 为真的时候得到 y, 反之得到 z 了。

int conditional(int x, int y, int z) {
    int flag = !!x;
    flag = (~flag) + 1;
    return (flag & y) | (~flag & z);
}

---

isLessOrEqual

• 描述：若 x <= y 返回 1，否则返回 0
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：24
• 难度：3

推导：

分三种情况讨论：

情况	x 的符号	y 的符号	结论
异号，x 为正	0	1	x > y，返回 0
异号，x 为负	1	0	x < y，返回 1
同号	相同	相同	比较 y + (-x) 的符号

前两种情况通过符号位判断，第三种情况利用 (y - x) >> 31 提取差的符号位。

int isLessOrEqual(int x, int y) {
    int signX = x >> 31;
    int signY = y >> 31;
    int same = signX ^ signY;             // 同号为 0，异号为 1
    int ver = ((~x) + 1 + y) >> 31;       // y - x 的符号位
    return (!same & !ver) | (same & !signY);
}

---

logicalNeg

• 描述：不使用 ! 运算符，实现逻辑非的功能
• 运算符限制：~ & ^ | + << >>
• 最大操作数：12
• 难度：4

推导：

提示：在 0/1 逻辑中，!x 等价于 x ^ 1。

! 的特性：x != 0 时返回 0，x == 0 时返回 1。

考虑 0 的特殊之处, 容易发现只有 0 的相反数还是 0，符号位不发生改变（0 和 -0 的符号位都是 0）。而对于任何非零值，x 和 -x 中至少有一个的符号位为 1。

因此用 x 的符号位 | (-x) 的符号位 即可区分零和非零，再异或 1 得到最终结果。

int logicalNeg(int x) {
    return (((((~x) + 1) >> 31) & 1) | ((x >> 31) & 1)) ^ 0x1;
}

---

howManyBits

• 描述：返回用二进制补码表示 x 所需的最少位数
• 运算符限制：! ~ & ^ | + << >>
• 最大操作数：90
• 难度：4

推导：

• 对于正数：最少位数 = 最高位 1 的位置 + 1（符号位）。
• 对于负数：最少位数 = 最高位 0 的位置 + 1（符号位）。

首先对负数取反，统一转化为"找最高位 1"的问题。

然后使用 二分查找 定位最高位 1 的位置。每次检查高半区是否有 1：

• 若有，则低半区的所有位都计入结果，同时将数据右移，缩窄搜索范围到高半区。
• 若无，则最高位 1 在低半区，继续下一轮查找。

推荐阅读：二分查找 (OI Wiki) ｜ 配套练习 (洛谷)

int howManyBits(int x) {
    int bit1, bit2, bit4, bit8, bit16;

    // 将负数取反，统一处理为正数
    int sign = ~((x >> 31) & 1) + 1;
    x = (x & ~sign) | (~x & sign);

    // 二分查找最高位 1
    bit16 = (!!(x >> 16)) << 4;
    x >>= bit16;

    bit8 = (!!(x >> 8)) << 3;
    x >>= bit8;

    bit4 = (!!(x >> 4)) << 2;
    x >>= bit4;

    bit2 = (!!(x >> 2)) << 1;
    x >>= bit2;

    bit1 = !!(x >> 1);
    x >>= bit1;

    // 累加所有分段长度 + 符号位 + 剩余位
    return bit16 + bit8 + bit4 + bit2 + bit1 + 1 + x;
}

---

floatScale2

• 描述：返回浮点数 uf 乘以 2 的位级等价表示
• 运算符限制：可以使用 if / while 等
• 最大操作数：30
• 难度：4

推导：

单精度浮点数表达式：

$$V=(-1{)}^{sign}\times 1.fraction\times 2^{e-bias}$$

乘以 2 的实质是将阶码 e 加 1，但需要考虑三种特殊情况：

情况	条件	处理方式
特殊值（NaN / ∞）	e == 0xFF	直接返回 uf，乘以 2 仍为 NaN 或 ∞
非规格化数（趋近 0）	e == 0	阶码固定为 −126，无法再 +1，改为将尾数左移 1 位来放大 2 倍
溢出为无穷	e + 1 == 0xFF	返回 s | 0x7F800000（带符号的无穷大）
正常情况	其余	e = e + 1，重组即可

unsigned floatScale2(unsigned uf) {
    unsigned s = uf & 0x80000000;
    unsigned e = (uf >> 23) & 0xFF;
    unsigned f = uf & 0x7FFFFF;

    if (e == 0xFF) return uf;                 // NaN 或无穷
    if (e == 0) return s | (uf << 1);         // 非规格化数

    e++;
    if (e == 0xFF) return s | 0x7F800000;     // 溢出为无穷

    return s | (e << 23) | f;
}

---

floatFloat2Int

• 描述：将浮点数 uf 强转为 int 的位级等价表示
• 运算符限制：可以使用 if / while 等
• 最大操作数：30
• 难度：4

推导：

浮点数表达式：

$$V=(-1{)}^{sign}\times 1.frac\times 2^{e-bias}$$

• e < 127（即 $e-127<0$）：浮点数绝对值小于 1.0，强转后为 0。
• e >= 158（即 $e-127\ge 31$）：超出 32 位 int 的表示范围（含 NaN 和无穷），返回 0x80000000u。

剩余情况中，frac 在浮点数中实际表示为 1.frac，转换时需先补上隐含的 1（即 f |= (1 << 23)），然后根据精度决定左移还是右移：

• e - 127 <= 23：精度足够，右移 23 - (e - 127) 位。
• e - 127 > 23：精度不足，低位补 0，左移 (e - 127) - 23 位。

最后根据符号位决定是否取反。

int floatFloat2Int(unsigned uf) {
    int res;
    unsigned s = uf & 0x80000000;
    int e = (uf >> 23) & 0xFF;
    unsigned f = uf & 0x7FFFFF;

    e -= 127;
    if (e >= 31) return 0x80000000u;   // NaN / ∞
    if (e < 0) return 0;               // 绝对值 < 1.0

    f |= (1 << 23);                     // 补上隐含的 1
    res = f;

    if (e < 23) res >>= (23 - e);      // 精度足够，右移
    else res <<= (e - 23);              // 精度不足，左移补 0

    if (s) res = ~res + 1;              // 负数：取补码

    return res;
}

---

floatPower2

• 描述：返回 $2.0^x$ 的单精度浮点数位级表示
• 运算符限制：可以使用 if / while 等
• 最大操作数：30
• 难度：4

推导：

同样基于浮点数公式 $V=(-1{)}^{sign}\times 1.frac\times 2^{e-bias}$，此题要构造的是纯 2 的幂次，因此 frac = 0，只需确定阶码。

分四种情况：

x 范围	所处区间	处理方式
[-126, 127]	规格化区间	直接令 e = x + 127，然后 (x + 0x7F) << 23
[-149, -127]	非规格化区间	由 0.f × 2−126 = f × 2−149 = 2x，得 f = 2x+149，即 1 << (x + 149)
< -149	下溢	返回 0
> 127	上溢	返回 +INF（0x7F800000）

unsigned floatPower2(int x) {
    if (x >= -126 && x <= 127)
        return (x + 0x7F) << 23;
    else if (x < -126 && x >= -149)
        return 1 << (x + 149);
    else if (x < -149)
        return 0;
    else
        return 0x7F800000;
}

---

参考资源

• CS:APP 3e — 官方 Lab 页面
• 二分查找 — OI Wiki
• WSL 环境配置教程

---

本文章内代码同步发布于 GitHub。如有疑问或更好的解法，欢迎在评论区交流讨论。