02 程序的表示和处理

下面是 LLM 生成的，做 DataLab 的时间自己简单看了一下

这一章最重要的事情，是建立一个稳定的“位级视角”：

一个 int 本质上是一串 32 位比特
同一串比特可以被解释成不同含义
无符号整数 unsigned
有符号整数 int
浮点数 float
Data Lab 训练的核心，不是做十进制算术，而是直接操纵这些比特

1. 信息就是位模式

在机器里，所有信息最终都是 bit pattern。

例如 32 位模式：

00000000 00000000 00000000 00100111

它可以表示：

作为无符号整数：39
作为有符号整数：39
作为字符序列的一部分：某些编码片段
作为浮点位模式：又会得到完全不同的解释

所以“值”不是脱离表示独立存在的；值依赖于解释规则。

2. 无符号数和有符号数

2.1 unsigned

若一个数用 w 位表示，那么无符号数范围是：

最小值：0
最大值：2^w - 1

例如 8 位：

00000000 = 0
11111111 = 255

无符号数的每一位权重都为正：

b[w-1] * 2^(w-1) + ... + b[1] * 2^1 + b[0] * 2^0

2.2 signed：补码 two's complement

CS:APP 里默认有符号整数采用补码表示。

对于 w 位补码：

最高位是符号相关位
正数和普通二进制一致
负数等于对应正数按位取反再加 1

例如 8 位：

5   = 00000101
-5  = 11111011

32 位时：

TMin = 0x80000000
TMax = 0x7fffffff

2.3 为什么补码这么重要

因为它让加法器统一处理正数和负数。

并且有一个非常重要的恒等式：

-x == ~x + 1

所以减法可以改写成：

x - y == x + (~y + 1)

这正是 Data Lab 里最常见的套路之一。

3. 常见位运算

在 Data Lab 中最常见的是：

&：按位与
|：按位或
^：按位异或
~：按位取反
<<：左移
>>：右移

3.1 `&`

只有对应位都为 1 时结果才为 1。

常见用途：保留某些位。

x & 0xFF

表示只保留最低 8 位。

3.2 `|`

对应位只要有一个为 1，结果就是 1。

常见用途：把某一位置为 1。

x | (1 << n)

3.3 `^`

相同为 0，不同为 1。

x ^ y

常见用途：

判断差异
翻转某一位
判断两个位模式是否相同

若 x == y，则：

x ^ y == 0

3.4 `~`

逐位翻转。

~0 == 0xFFFFFFFF

在补码机器上，这也就是 -1。

4. 移位

4.1 左移 `x << n`

整体向左移动 n 位，右侧补 0。

通常可以理解为乘以 2^n，但要注意：

可能溢出
对有符号数不能机械套用十进制直觉

4.2 右移 `x >> n`

整体向右移动 n 位。

需要区分两种：

逻辑右移：左边补 0
算术右移：左边补符号位

Data Lab 一般按 算术右移 来思考 int。

因此在 32 位补码下：

x >> 31

非常有用：

若 x >= 0，结果是 0
若 x < 0，结果是 0xFFFFFFFF

也就是它可以直接产生一个“全 0 / 全 1”的掩码。

5. 掩码 mask 的思维方式

做 Data Lab 时，经常不允许写 if，所以要把条件判断转成掩码运算。

5.1 全 0 和全 1

0      // 全 0
~0     // 全 1

5.2 条件选择

如果 mask 是：

全 1：选 a
全 0：选 b

那么可以写成：

(mask & a) | (~mask & b)

这是 Data Lab 里实现 conditional 一类题的标准套路。

6. 一些高频等式

这些式子几乎需要背下来：

~x + 1          // -x
x + (~y + 1)    // x - y
x ^ x           // 0
x & 0           // 0
x | 0           // x
x & ~0          // x
x ^ 0           // x

两个尤其常见：

x & (-x)

它能取出最低位的 1。

以及：

x & (x - 1)

它能消掉最低位的 1。

7. 补码里的特殊值

7.1 `-1`

-1 == 0xFFFFFFFF

也就是全 1。

7.2 `TMin`

TMin == 0x80000000

它非常特殊，因为：

~TMin + 1 == TMin

不是因为它真等于自己的相反数，而是因为在 32 位补码里发生了溢出。

这也是很多题目容易出错的地方。

8. 溢出

8.1 无符号溢出

无符号运算本质上是模 2^w 运算。

例如 8 位下：

255 + 1 == 0

因为高位被截断。

8.2 有符号溢出

补码加法在以下情况会溢出：

两个正数相加得到负数
两个负数相加得到正数

也就是：

x 和 y 同号
sum 与它们异号

这在 isLessOrEqual、addOK 这类题目中经常要单独处理。

9. signed 和 unsigned 的差异

同样的位模式，解释方式不同，值就不同。

例如：

11111111 11111111 11111111 11111111

作为 unsigned：4294967295
作为 int：-1

这说明：

位模式本身没有“正负”，正负来自解释规则。

9.1 C 里混用 signed / unsigned 要小心

一旦一个表达式里混入 unsigned，C 常常会把另一个操作数也转换成无符号数再比较或运算。

因此类似：

-1 < 1U

结果并不是直觉上的真，而可能是把 -1 先转成很大的无符号数再比较。

这类现象在 CS:APP 中非常重要，因为它提醒我们：C 的比较行为依赖类型提升和转换规则。

10. 浮点数是另一套编码规则

float 不是补码，它遵循 IEEE 754 单精度格式。

32 位单精度通常拆成：

1 位符号位 s
8 位指数 exp
23 位小数部分 frac

结构上可以记成：

[s][ exp ][ fraction ]

10.1 规格化数 normalized

当 exp 既不是全 0 也不是全 1 时：

value = (-1)^s * (1.fraction) * 2^(exp - Bias)

其中单精度的 Bias = 127。

10.2 非规格化数 denormalized

当 exp == 0 且 frac != 0 时：

value = (-1)^s * (0.fraction) * 2^(1 - Bias)

它用于表示非常接近 0 的数。

10.3 特殊值

exp == 0 && frac == 0：+0 或 -0
exp == 0xFF && frac == 0：+inf 或 -inf
exp == 0xFF && frac != 0：NaN

所以浮点题的关键，不是“算十进制值”，而是按字段拆解位模式。

11. 做 Data Lab 时的思考方式

做题时不要先想十进制公式，而要先问：

我想识别的性质是什么？
是否为 0
是否同号
是否在区间内
是否溢出
这个性质能否转成位级判定？
相等：x ^ y == 0
负数：最高位为 1
减法：x + (~y + 1)
结果是逻辑值 0/1，还是掩码 0x00000000/0xFFFFFFFF？
能否用掩码拼出最终结果？

12. 一份最常用的小抄

~x + 1              // -x
x + (~y + 1)        // x - y
x >> 31             // 符号掩码
!(x ^ y)            // 判断相等
(mask & a) | (~mask & b)   // 条件选择
(1 << n) - 1        // 低 n 位全 1
x & (x - 1)         // 消去最低位的 1
x & (~x + 1)        // 取最低位的 1

13. 一个实践建议

在 Data Lab 里，建议频繁做两件事：

用 ishow / fshow 看具体位模式的解释
用自定义的小工具打印小范围输入的结果表

这样做的好处是：

能快速确认表达式行为
能尽早发现自己把逻辑值和掩码混淆了
能看出边界值如 0、-1、TMin、TMax 的特殊性

从这个角度说，Data Lab 本质上不是“写答案”，而是在训练你建立对位模式的直觉。