第 2 章：信息的表示和处理

主题：信息的表示和处理 (Representing and Manipulating Information)
目标：理解计算机如何用位表示整数、浮点数和地址，并掌握溢出、转换、舍入等底层规则。

1. 核心视角

所有数据在机器中本质都是位串。

flowchart LR
    A["位串<br/>Bits"] --> B["无符号整数<br/>Unsigned"]
    A --> C["补码整数<br/>Two's Complement"]
    A --> D["浮点数<br/>IEEE Floating Point"]
    A --> E["地址/指针<br/>Address"]
    A --> F["指令编码<br/>Instruction"]

同一段位串，解释方式不同，含义就不同。

2. 信息存储基础

常见大小：

C 标准只规定最小范围，不保证所有平台大小完全一致。CSAPP 第 2 章默认主要讨论 x86-64 环境。

3. 十六进制

4 个二进制位对应 1 个十六进制位。

4. 字节序

多字节对象在内存中的字节排列方式称为字节序 (Byte Ordering)。

假设整数：

0x01234567

flowchart LR
    A["整数 0x01234567"] --> B["小端：67 45 23 01"]
    A --> C["大端：01 23 45 67"]

x86-64 使用小端法。调试内存时看到字节顺序反过来，通常就是小端造成的。

5. 位级运算

常用技巧：

逻辑运算和位级运算不同：

6. 移位

右移差异：

x = 10000000

逻辑右移 1 位：01000000
算术右移 1 位：11000000

对无符号数，右移是逻辑右移。
对有符号负数，C 标准未完全保证，但多数机器使用算术右移。

7. 无符号整数

w 位无符号整数的取值范围：

0 <= x <= 2^w - 1

位向量：

x = [x_{w-1}, ..., x_1, x_0]

解释为：

B2U_w(x) = sum(x_i * 2^i), i = 0..w-1

示例：

8. 补码整数

w 位补码整数的取值范围：

-2^(w-1) <= x <= 2^(w-1) - 1

位向量解释为：

B2T_w(x) = -x_{w-1} * 2^(w-1) + sum(x_i * 2^i), i = 0..w-2

4 位补码示例：

关键点：

非对称性：补码最小值没有对应的正数。
例如 4 位中 -8 存在，但 +8 不存在。

9. 有符号与无符号转换

C 中有符号数和无符号数转换时，底层位不变，解释方式改变。

flowchart LR
    A["位串 1111"] --> B["unsigned: 15"]
    A --> C["signed: -1"]

转换规则：

典型坑：

int x = -1;
unsigned y = 0;
printf("%d\n", x < y);   // 通常输出 0

原因：x 被转换为无符号数，-1 变为 UINT_MAX。

10. 扩展与截断

10.1 扩展

补码符号扩展保持数值不变。

4 位：1011 = -5
8 位：11111011 = -5

10.2 截断

截断就是丢弃高位。

0x12345678 截断为 16 位：0x5678

数学上等价于：

x mod 2^k

截断后如果再按补码解释，符号和值都可能改变。

11. 整数加法与溢出

机器整数运算通常是模运算。

w 位无符号加法：
(x + y) mod 2^w

无符号加法溢出：

补码加法溢出：

flowchart TD
    A["补码加法 x + y"] --> B{"x,y 同号？"}
    B -- 否 --> C["不会溢出"]
    B -- 是 --> D{"结果符号是否改变？"}
    D -- 是 --> E["溢出"]
    D -- 否 --> F["未溢出"]

12. 取反与乘法

补码取负：

-x = ~x + 1

特殊情况：

-TMin == TMin

原因：TMin 没有可表示的正数对应值。

乘法：

w 位整数乘法只保留低 w 位

对于乘以 2 的幂：

有符号除以 2 的幂时，编译器常加偏置：

(x + (1 << k) - 1) >> k    // x < 0 时用于向 0 舍入

13. 整数安全问题

更稳妥的写法：

for (size_t i = n; i > 0; i--) {
    size_t idx = i - 1;
    /* use idx */
}

14. 浮点数表示

IEEE 浮点数 (IEEE Floating Point) 由三部分组成：

flowchart LR
    A["浮点位串"] --> B["符号位 s"]
    A --> C["阶码 exp"]
    A --> D["尾数 frac"]

通用形式：

V = (-1)^s * M * 2^E

常见格式：

15. 浮点数三类编码

flowchart TD
    A["查看 exp"] --> B{"全 0？"}
    B -- 是 --> C{"frac 全 0？"}
    C -- 是 --> D["零"]
    C -- 否 --> E["非规格化数"]
    B -- 否 --> F{"exp 全 1？"}
    F -- 是 --> G{"frac 全 0？"}
    G -- 是 --> H["无穷"]
    G -- 否 --> I["NaN"]
    F -- 否 --> J["规格化数"]

16. 浮点舍入

常见舍入模式：

向偶数舍入：

正好在中间时，选择最低有效位为偶数的结果。

17. 浮点运算性质

浮点运算近似实数运算，但不满足所有数学性质。

示例：

(3.14 + 1e20) - 1e20   // 可能得到 0
3.14 + (1e20 - 1e20)   // 得到 3.14

18. C 中的强制转换

精度关系：

因此：

int -> double 通常精确
int -> float 可能不精确
long -> double 可能不精确

19. Data Lab 关联

labs/data-lab 主要训练本章内容。

20. 常见坑