计算机系统 - 数据表达

一、整数编码

计算机中整数有两种基本编码方式：无符号编码（只表示非负整数）和补码编码（表示有符号整数，含负数）。两者共享同样的二进制位，但解读规则不同——同一串比特，用不同编码会得到不同的数值。

---

1.1 无符号数编码（Unsigned）

B2U 函数定义

对一个 $w$ 位的二进制向量 $\vec{x} = [x_{w-1},\, x_{w-2},\, \dots,\, x_0]$，无符号解码函数 B2U（Binary to Unsigned）定义为：

$$B2U_w(\vec{x}) = \sum_{i=0}^{w-1} x_i \cdot 2^i$$

每一位的权重都是正的 $2^i$，所有位做简单的加权求和。

示例（$w = 4$）

二进制	计算过程	十进制（无符号）
0000	$0$	0
0001	$2^0 = 1$	1
0101	$2^2 + 2^0 = 5$	5
1111	$2^3 + 2^2 + 2^1 + 2^0 = 15$	15
1000	$2^3 = 8$	8

取值范围

$$0 \leq B2U_w(\vec{x}) \leq 2^w - 1$$

位宽 $w$	最小值	最大值 $UMax_w$
8	0	255
16	0	65 535
32	0	4 294 967 295

直觉：无符号编码就是我们日常做的"二进制转十进制"，没有任何特殊处理，$w$ 位能表示 $0$ 到 $2^w - 1$ 共 $2^w$ 个值。

---

1.2 二进制补码编码（Two's Complement）

补码是现代计算机表示有符号整数的标准方式，也是 CSAPP 的重点。

B2T 函数定义

对同样的 $w$ 位二进制向量 $\vec{x} = [x_{w-1},\, x_{w-2},\, \dots,\, x_0]$，补码解码函数 B2T（Binary to Two's complement）定义为：

$$B2T_w(\vec{x}) = -x_{w-1} \cdot 2^{w-1} + \sum_{i=0}^{w-2} x_i \cdot 2^i$$

和 B2U 唯一的区别：最高位 $x_{w-1}$ 的权重是负的 $-2^{w-1}$，其余低位的权重仍然是正的。

示例（$w = 4$）

二进制	计算过程	十进制（补码）
0000	$0$	0
0001	$2^0 = 1$	1
0101	$2^2 + 2^0 = 5$	5
0111	$2^2 + 2^1 + 2^0 = 7$	7（$TMax_4$）
1000	$\mathbf{-2^3} = -8$	−8（$TMin_4$）
1001	$-2^3 + 2^0 = -7$	−7
1111	$-2^3 + 2^2 + 2^1 + 2^0 = -1$	−1

注意 1000 和 0111 的对比：最高位一翻，数值从 $+7$ 变成 $-8$，这就是最高位"负权重"的威力。

取值范围

$$-2^{w-1} \leq B2T_w(\vec{x}) \leq 2^{w-1} - 1$$

位宽 $w$	$TMin_w$（最小值）	$TMax_w$（最大值）
8	−128	127
16	−32 768	32 767
32	−2 147 483 648	2 147 483 647

不对称性：$|TMin| = |TMax| + 1$，即负数比正数多一个（因为 $0$ 占了一个正数的编码位置）。这一性质会导致补码取反的陷阱：-TMin 在同位宽下会溢出，仍然等于 TMin。

---

1.3 补码的本质：最高位的负权重

理解补码最关键的一句话：

补码和无符号数的唯一区别，就是最高位（MSB）的权重从 $+2^{w-1}$ 变成了 $-2^{w-1}$。

把两个公式放在一起对比：

	无符号 $B2U$	补码 $B2T$
最高位权重	$+2^{w-1}$	$\mathbf{-2^{w-1}}$
其余位权重	$+2^i$（不变）	$+2^i$（不变）
最高位含义	单纯的"大数值贡献"	符号位：决定正负

直观理解：

• 当 $x_{w-1} = 0$ 时，负权重项为 $0$，B2T 和 B2U 结果完全相同——正数在两种编码下表现一致。
• 当 $x_{w-1} = 1$ 时，负权重项 $-2^{w-1}$ 把整个数值拉到负半轴。低位的正权重在"部分抵消"这个大的负值，越抵消越接近 $0$（所以 1111...1 = $-1$，而非最小负数）。

为什么 1111...1 = −1 而不是最小值？

以 $w = 4$ 为例：

$$B2T_4(1111) = \underbrace{-2^3}_{-8} + \underbrace{2^2 + 2^1 + 2^0}_{+7} = -1$$

低位全 1 产生的正权重 ($+7$) 几乎完全抵消了最高位的负权重 ($-8$)，只差 $1$。所以全 1 不是最小值，而是 $-1$。

相反，1000 才是最小值（$TMin$），因为只有负权重在起作用，没有任何正位去抵消它。

补码的时钟模型：模运算的圆盘

补码的数值空间本质上是一个环——就像时钟盘一样首尾相连。$w$ 位二进制的所有运算都在 $\mod 2^w$ 下进行，$2^w$ 个编码均匀排列在圆盘上：

flowchart LR
    subgraph 正半边
        direction LR
        n0["0\n0000"] --> n1["+1\n0001"] --> n2["+2\n0010"] --> n3["+3\n0011"]
        n3 --> n4["+4\n0100"] --> n5["+5\n0101"] --> n6["+6\n0110"] --> n7["+7\n0111"]
    end

    subgraph 负半边
        direction RL
        m8["-8\n1000"] --> m7["-7\n1001"] --> m6["-6\n1010"] --> m5["-5\n1011"]
        m5 --> m4["-4\n1100"] --> m3["-3\n1101"] --> m2["-2\n1110"] --> m1["-1\n1111"]
    end

    n7 -->|"⚡ 正溢出\n+7 → −8"| m8
    m1 -->|"−1 + 1 = 0"| n0

    linkStyle 14 stroke:#d62728,stroke-width:3px
    linkStyle 15 stroke:#2ca02c,stroke-width:3px

关键观察：

• $+7$（0111）的下一个就是 $-8$（1000） —— 正数的最大值 $TMax$ 加 $1$ 就"翻转"到负数的最小值 $TMin$，这就是正溢出。
• $-1$（1111）的下一个是 $0$（0000） —— 从整数视角看，$-1 + 1 = 0$，完全自洽。
• $-8$（1000）减 $1$ 回到 $+7$（0111） —— 这就是负溢出。

模运算本质：$w$ 位补码的加减法，其实就是在一个周长为 $2^w$ 的圆盘上"顺时针/逆时针走步"。走过边界时不会报错，只会绕回来——这就是整数溢出的几何含义。和 12 小时制的时钟一模一样：$11$ 点再过 $2$ 小时不是 $13$ 点，而是 $1$ 点。

与原码、反码的关系

编码方式	缺点	补码的改进
原码（符号 + 绝对值）	有 $+0$ 和 $-0$ 两个零	补码只有一个零
反码（符号位不变，其余取反）	仍有双零问题	补码消除了双零
补码（负权重定义）	—	加法器天然支持，硬件实现最简单

硬件上的优势：补码的加法和无符号加法共用同一个加法器电路——CPU 不需要关心操作数是有符号还是无符号，同样的二进制加法就能得出正确结果（溢出行为除外）。这是补码被选为标准有符号编码的根本原因。

---

1.4 有符号与无符号的映射关系（T2U / U2T）

同一个 $w$ 位二进制向量，在两种编码下的数值关系：

$$B2U_w(\vec{x}) = \begin{cases} B2T_w(\vec{x}) & \text{若 } x_{w-1} = 0 \text{（非负数，解读一致）} \\[4pt] B2T_w(\vec{x}) + 2^w & \text{若 } x_{w-1} = 1 \text{（补码为负，无符号 = 补码值 } + 2^w\text{）} \end{cases}$$

T2U 与 U2T 转换公式

T2U（有符号 → 无符号）：

$$T2U_w(x) = \begin{cases} x & x \geq 0 \\ x + 2^w & x < 0 \end{cases}$$

U2T（无符号 → 有符号）：

$$U2T_w(u) = \begin{cases} u & u \leq 2^{w-1} - 1 \text{（即 } u \leq TMax\text{）} \\ u - 2^w & u \geq 2^{w-1} \text{（即 } u > TMax\text{）} \end{cases}$$

两个公式互为逆运算。位模式始终不变，只是在圆盘上换了一套编号。

举例（$w = 4$）：

转换	输入	输出	计算
T2U	$-6$	$10$	$-6 + 16 = 10$
T2U	$5$	$5$	非负，不变
T2U	$-1$	$15$	$-1 + 16 = 15$
U2T	$10$	$-6$	$10 - 16 = -6$（$10 > 7$）
U2T	$5$	$5$	$5 \leq 7$，不变

⚠️ 经典陷阱

陷阱一：有符号 vs 无符号比较

-1 < 0U   // false！

-1 被隐式转为 unsigned：位模式 0xFFFFFFFF → 无符号 $4294967295$，比 $0$ 大。

陷阱二：unsigned 的循环永远不会 < 0

unsigned i;
for (i = n - 1; i >= 0; i--)  // ⚠️ 死循环！unsigned 永远 >= 0
    // ...

当 i 减到 0 再减 1，结果不是 $-1$ 而是 $UMax$（圆盘绕回去了），条件永远为真。

陷阱三：size_t（无符号）相减可能绕回

// strlen() 返回 size_t（无符号）
if (strlen(a) - strlen(b) >= 0)  // ⚠️ 永远为真！

无符号减法不会产生负数。如果 strlen(a) < strlen(b)，结果会绕回成一个巨大的正数。正确写法：strlen(a) >= strlen(b)。

陷阱四：$TMin$ 取负溢出

int x = INT_MIN;     // -2147483648
int y = -x;          // 仍然是 -2147483648！

$-TMin$ 在补码中无法表示（因为 $|TMin| > TMax$），溢出后绕回自身。在圆盘上看：$TMin$ 的对称点超出了正半边的最大值，又回到了 $TMin$。

C 语言中的隐式转换规则：当有符号与无符号数混合运算时，C 会将有符号数隐式转为无符号数（位模式不变，解读规则变了）……几乎所有的 unsigned 陷阱都来源于此。

---

二、位数转换：扩展与截断

当不同位宽的整数需要互相赋值时，位数会发生变化。核心问题：增减比特时，如何保持数值不变（或可预测地变化）？

---

2.1 符号扩展（Sign Extension）—— 小位宽 → 大位宽（有符号数）

将一个 $w$ 位补码数扩展到 $w' > w$ 位时，在高位填充符号位（即 MSB 的值）。

规则

$$[x_{w-1},\, x_{w-2},\, \dots,\, x_0] \xrightarrow{\text{符号扩展}} [\underbrace{x_{w-1},\, x_{w-1},\, \dots,\, x_{w-1}}_{w'-w \text{ 个}},\, x_{w-1},\, x_{w-2},\, \dots,\, x_0]$$

一句话：正数前面补 0，负数前面补 1。

示例（4 位 → 8 位）

4 位补码	十进制	符号扩展到 8 位	验证十进制
0101	$+5$	0000 0101	$+5$ ✓
0111	$+7$	0000 0111	$+7$ ✓
1010	$-6$	1111 1010	$-6$ ✓
1000	$-8$	`1111 1000$	$-8$ ✓
1111	$-1$	1111 1111	$-1$ ✓

注意 $-6$（1010）扩展后变成 1111 1010，看起来多了很多 1，但数值完全不变。

为什么符号扩展是正确的？

以负数为例理解（正数补 0 显然正确，略过）。

将 4 位补码 $-6$（1010）扩展到 5 位（11010），验证 B2T 值不变：

原始 4 位：

$$B2T_4(1010) = -2^3 + 2^1 = -8 + 2 = -6$$

扩展到 5 位（高位补 1）：

$$B2T_5(11010) = -2^4 + 2^3 + 2^1 = -16 + 8 + 2 = -6 \quad ✓$$

本质：新增的高位 1 贡献了 $-2^4$，但原来的最高位从"负权重 $-2^3$"变成了"正权重 $+2^3$"，两者之差恰好抵消：

$$-2^4 + 2^3 = -16 + 8 = -8 = -2^3 \quad \text{（等于原来的负权重）}$$

每多扩展一位，这个"$-2^k + 2^{k-1} = -2^{k-1}$"的抵消关系都成立，所以可以一直往高位补符号位。

数学归纳：每扩展一位，新增一个负权重 $-2^k$，同时原最高位变为正权重 $+2^{k-1}$，两者之和 $= -2^{k-1}$，与扩展前的最高位负权重相同。因此，扩展任意多位都不改变数值。

---

2.2 零扩展（Zero Extension）—— 小位宽 → 大位宽（无符号数）

无符号数的扩展更简单：高位全部补 0。

$$[x_{w-1},\, x_{w-2},\, \dots,\, x_0] \xrightarrow{\text{零扩展}} [\underbrace{0,\, 0,\, \dots,\, 0}_{w'-w \text{ 个}},\, x_{w-1},\, x_{w-2},\, \dots,\, x_0]$$

示例（4 位 → 8 位）

4 位无符号	十进制	零扩展到 8 位	验证
0101	5	0000 0101	5 ✓
1010	10	0000 1010	10 ✓
1111	15	0000 1111	15 ✓

因为 B2U 公式中每一位的权重都是正的，高位补 0 不增加任何权重值，数值自然不变。

对比：符号扩展 vs 零扩展

	符号扩展	零扩展
适用类型	有符号数（补码）	无符号数
填充内容	符号位（MSB）的值	全 0
正数时	补 0（和零扩展一样）	补 0
负数时	补 1	不适用（无符号没有负数）
x86 指令	movsx / movsxd（sign extend）	movzx（zero extend）

# x86-64 示例
movsbl  %al, %eax    # 将 al（8位有符号）符号扩展到 eax（32位）
movzbl  %al, %eax    # 将 al（8位无符号）零扩展到 eax（32位）
movslq  %eax, %rax   # 将 eax（32位有符号）符号扩展到 rax（64位）

C 编译器的选择：char → int 默认使用符号扩展（因为 char 默认有符号）；unsigned char → int 使用零扩展。int → long 使用符号扩展。

---

2.3 截断（Truncation）—— 大位宽 → 小位宽

将 $w$ 位截断为 $k < w$ 位时，直接丢弃高 $w - k$ 位，只保留低 $k$ 位。

$$[x_{w-1},\, \dots,\, x_k,\, x_{k-1},\, \dots,\, x_0] \xrightarrow{\text{截断为 } k \text{ 位}} [x_{k-1},\, \dots,\, x_0]$$

直觉：十进制的"截断"

先想十进制：把 $\textbf{1}234$ 保留后 $2$ 位得 $34$。这等价于 $1234 \mod 100 = 34$——砍掉高位数字，就是对 $10^k$ 取模（$k$ = 保留的位数）。

二进制完全一样：把 0001 0101（$21$）保留低 $4$ 位得 0101（$5$），就是 $21 \mod 2^4 = 21 \mod 16 = 5$。砍掉高位 bit = 对 $2^k$ 取模。

所谓"取模"，就是用 $2^k$ 去除，只留余数。余数恰好就是低 $k$ 位保存的信息，高位对低 $k$ 位没有任何贡献（因为高位每一位的权重都是 $2^k$ 的整倍数，被模运算整除了）。

无符号截断

$$B2U_k([x_{k-1},\, \dots,\, x_0]) = B2U_w(\vec{x}) \mod 2^k$$

补码截断

先按无符号截断（取模），然后将结果转回补码解读：

$$B2T_k([x_{k-1},\, \dots,\, x_0]) = U2T_k(B2U_w(\vec{x}) \mod 2^k)$$

示例（8 位 → 4 位）

8 位二进制	无符号值	截断后低 4 位	无符号结果	补码结果
0001 0101	21	0101	5（$21 \mod 16$）	5
1111 1010	250	1010	10（$250 \mod 16$）	−6
0000 1111	15	1111	15（$15 \mod 16$）	−1
0001 0011	19	0011	3（$19 \mod 16$）	3

截断不保值：和扩展不同，截断几乎一定会改变数值（除非高位本来就全是 0 或全是符号位）。截断本质就是强制绕圆盘——用更小的圆盘（$2^k$ 个编码）去"套"一个大数，自然只能保留余数。

截断何时"安全"？

只有当原始值恰好在目标位宽的表示范围内时，截断才不改变数值：

• 无符号：$0 \leq x < 2^k$ 时截断不变
• 补码：$-2^{k-1} \leq x \leq 2^{k-1} - 1$ 时截断不变

int x = 53;
short sx = (short)x;   // 53 在 short 范围内，安全
int y = 100000;
short sy = (short)y;   // 100000 超出 short 范围（-32768~32767），截断后值变了！
// sy = 100000 mod 65536 = 34464 → 补码解读 = -31072

---

2.4 C 语言中的隐式扩展与截断

C 编译器在赋值和运算时自动处理位宽转换：

C 操作	位宽变化	编译器行为
char → int	8 → 32	符号扩展（默认 char 有符号）
unsigned char → int	8 → 32	零扩展
short → int	16 → 32	符号扩展
int → long	32 → 64	符号扩展
int → short	32 → 16	截断（丢弃高16位）
int → char	32 → 8	截断（丢弃高24位）

⚠️ 同时涉及扩展 + 类型转换时的顺序

当位宽变化和有符号/无符号转换同时发生时，C 的规则是先扩展位宽，再转换类型：

short sx = -12345;            // 16位补码：0xCFC7
unsigned uy = sx;             // short → unsigned (16位 → 32位 + 有符号→无符号)

// 实际执行顺序：
// ① 先符号扩展：short(-12345) → int(-12345)   位模式：0xFFFFCFC7
// ② 再转 unsigned：int(-12345) → unsigned      位模式不变：0xFFFFCFC7 = 4294954951

如果先截断再扩展，或先转类型再扩展，结果可能完全不同。C 标准规定的顺序是先改大小，再改符号。

---

三、整数运算

硬件加法器的位宽是固定的（$w$ 位），当运算结果超出 $w$ 位能表示的范围时，高位被丢弃——这就是溢出。本章讨论在这种有限位宽下，加法、取反、乘法、除法分别如何工作。

---

3.1 无符号加法（UAdd）

定义

两个 $w$ 位无符号数相加，真实算术结果可能需要 $w+1$ 位。硬件只保留低 $w$ 位，等价于 $\mod 2^w$：

$$UAdd_w(u,\, v) = (u + v) \mod 2^w$$

溢出判断

$$UAdd_w(u,\, v) = \begin{cases} u + v & \text{若 } u + v < 2^w \text{（正常）} \\ u + v - 2^w & \text{若 } u + v \geq 2^w \text{（溢出，丢掉进位）} \end{cases}$$

检测溢出：如果结果 $s = UAdd(u, v)$，则溢出 $\iff$ $s < u$（或 $s < v$）。

直觉：两个正数相加，结果反而比其中一个还小，一定是绕了一圈。

示例（$w = 4$，范围 $0 \sim 15$）

$u$	$v$	真实和	$UAdd_4$	溢出？
9	5	14	14	✗
12	9	21	$21 - 16 = 5$	✓
15	1	16	$16 - 16 = 0$	✓

圆盘视角：从 $u$ 出发顺时针走 $v$ 步，如果越过 $0$（从 $15$ 绕回 $0$），就是溢出。

---

3.2 补码加法（TAdd）

定义

补码加法的位级运算和无符号加法完全相同（CPU 用同一个加法器），只是对结果按补码解读：

$$TAdd_w(u,\, v) = U2T_w\big((u + v) \mod 2^w\big)$$

展开后：

$$TAdd_w(u,\, v) = \begin{cases} u + v - 2^w & \text{若 } u + v \geq 2^{w-1} \text{（正溢出：和太大，绕到负数）} \\ u + v & \text{若 } -2^{w-1} \leq u + v < 2^{w-1} \text{（正常）} \\ u + v + 2^w & \text{若 } u + v < -2^{w-1} \text{（负溢出：和太小，绕到正数）} \end{cases}$$

溢出判断

溢出类型	条件	结果表现
正溢出	$u > 0$ 且 $v > 0$ 且 $s \leq 0$	两正数之和成了负数
负溢出	$u < 0$ 且 $v < 0$ 且 $s \geq 0$	两负数之和成了正数
不溢出	符号不同，或同号但结果符号一致	—

关键：正 + 正 = 负 → 正溢出；负 + 负 = 正 → 负溢出。一正一负永远不会溢出（因为结果的绝对值不可能超出范围）。

示例（$w = 4$，范围 $-8 \sim +7$）

$u$	$v$	真实和	$TAdd_4$	溢出类型
5	3	8	$8 - 16 = -8$	正溢出
−7	−3	−10	$-10 + 16 = 6$	负溢出
5	−3	2	2	无
−5	3	−2	−2	无

圆盘视角：从 $u$ 出发走 $v$ 步，越过 $+7 \to -8$ 的边界就是正溢出，越过 $-8 \to +7$ 的边界就是负溢出。

💡 实战：算法题"不开 long long 见祖宗"

写算法题时，两个 int 相加或相乘的结果超过 $2^{31} - 1$（约 $2.1 \times 10^9$），就会正溢出变成负数——这就是补码加法/乘法的圆盘绕回：

int a = 1000000000;  // 10^9
int b = 1000000000;
int c = a + b;       // 真实值 2×10^9，超过 TMax(int) = 2147483647
                     // 结果：c = 2000000000 - 2^32 = -294967296（负数！）

原因就在 $TAdd$：真实和 $\geq 2^{31}$ 时，减去 $2^{32}$ 绕到负半边。解决方案：换成 long long（64 位），$TMax$ 变为 $9.2 \times 10^{18}$，溢出的圆盘大了 $2^{32}$ 倍。

---

3.3 取反（Negation）

无符号取反（UNeg）

$$UNeg_w(u) = \begin{cases} 0 & \text{若 } u = 0 \\ 2^w - u & \text{若 } u > 0 \end{cases}$$

圆盘上 $u$ 关于 $0$ 的对称点：从 $0$ 往反方向走 $u$ 步。

补码取反（TNeg）

$$TNeg_w(x) = \begin{cases} TMin_w & \text{若 } x = TMin_w \text{（特殊！取反后溢出，回到自身）} \\ -x & \text{其他情况} \end{cases}$$

$TMin$ 的取反是唯一的陷阱：$-(-8) = 8$，但 4 位补码最大只能表示 $7$，溢出后绕回 $-8$。

位级操作求补码取反（实用技巧）：

$$-x = \,\sim\!x + 1 \quad \text{（按位取反再加 1）}$$

// 例：x = 5 (0101)
// ~x = 1010 (补码 -6)
// ~x + 1 = 1011 (补码 -5) ✓

---

3.4 无符号乘法（UMult）

两个 $w$ 位无符号数相乘，真实结果可能需要 $2w$ 位。硬件只保留低 $w$ 位：

$$UMult_w(u,\, v) = (u \times v) \mod 2^w$$

示例（$w = 4$）

$u$	$v$	真实积	$UMult_4$
5	3	15	15
5	5	25	$25 \mod 16 = 9$
15	15	225	$225 \mod 16 = 1$

---

3.5 补码乘法（TMult）

补码乘法的结果同样截断为低 $w$ 位，但按补码解读：

$$TMult_w(u,\, v) = U2T_w\big((u \times v) \mod 2^w\big)$$

关键性质：无符号乘法和补码乘法的位级结果完全相同——同样的 $w$ 位二进制模式，只是解读方式不同。

示例（$w = 4$）

$u$（补码）	$v$（补码）	真实积	截断后位模式	补码解读	无符号解读
5	3	15	1111	−1	15
−3	−5	15	1111	−1	15
−1	7	−7	1001	−7	9

注意 $5 \times 3 = 15$，但 4 位补码中 1111 = $-1$，不是 $15$。乘法非常容易溢出，因为结果增长是平方级的。

---

3.6 乘以常数：编译器的移位优化

整数乘法指令在 CPU 上通常需要 3~10 个时钟周期，而移位和加法只需 1 个周期。编译器会自动将乘以常数优化为移位 + 加减法的组合。

核心：乘以 $2^k$ = 左移 $k$ 位

$$x \times 2^k = x \ll k$$

这对无符号和补码都成立（溢出时高位自然丢弃，与截断行为一致）。

分解任意常数

编译器将常数拆成 $2$ 的幂之和（或差），用移位 + 加减组合：

乘法	分解	移位 + 加减	汇编
x * 3	$2 + 1$	$(x \ll 1) + x$	leaq (%rax,%rax,2), %rax
x * 5	$4 + 1$	$(x \ll 2) + x$	leaq (%rax,%rax,4), %rax
x * 6	$4 + 2$	$(x \ll 2) + (x \ll 1)$	移位 + 加法
x * 7	$8 - 1$	$(x \ll 3) - x$	移位 + 减法
x * 12	$8 + 4$	$(x \ll 3) + (x \ll 2)$	移位 + 加法
x * 15	$16 - 1$	$(x \ll 4) - x$	移位 + 减法

lea 指令的再次登场：回忆第一篇笔记中 lea 被编译器借用做乘加优化——leaq (%rax,%rax,2), %rax 就是 rax = rax * 3，这正是上面的常数乘法优化。

---

3.7 除以 2 的幂：右移

先搞清两种取整

整数除法遇到除不尽时，有两种常见的舍入方式：

取整方式	含义	$7 \div 2$	$-7 \div 2$
向下取整（floor，$\lfloor \rfloor$）	往数轴左边（负无穷方向）取最近整数	$3$（$3.5 \to 3$）	$-4$（$-3.5 \to -4$）
向零取整（truncate）	往靠近零的方向取最近整数	$3$（$3.5 \to 3$）	$-3$（$-3.5 \to -3$）

正数时两者一致（都是砍掉小数部分）。负数时不同：$-3.5$ 向下取整是 $-4$（更小），向零取整是 $-3$（更靠近零）。C 语言的 / 运算符采用向零取整。

无符号除法：逻辑右移（补 0）

$$u \div 2^k = u \gg k \quad \text{（逻辑右移，结果向下取整/截断）}$$

unsigned u = 13;   // 1101
u >> 1;            // 0110 = 6  （13/2 = 6.5 → 6）
u >> 2;            // 0011 = 3  （13/4 = 3.25 → 3）

逻辑右移总是向零方向舍入（floor），对非负数来说这就是正常的整除截断。

补码除法：算术右移（补符号位）

对有符号数，右移使用算术右移（高位补符号位）：

$$x \gg k = \lfloor x / 2^k \rfloor \quad \text{（向下取整，即向负无穷方向舍入）}$$

问题：对负数来说，"向下取整"≠ "向零取整"：

int x = -7;   // 补码 1...11001
x >> 1;       // 算术右移：1...11100 = -4  （-7/2 = -3.5 → 向下取整 = -4）
// 但 C 语言要求整数除法向零取整：-7/2 应该 = -3

偏置修正（Biasing）

为了让算术右移得到向零取整（C 的除法语义），对负数需要在移位前加一个偏置：

$$\text{对 } x < 0：\quad \lfloor (x + 2^k - 1) / 2^k \rfloor = \lceil x / 2^k \rceil$$

即：先加 $(2^k - 1)$，再做算术右移。

// 编译器将 x / 4（x 为有符号）翻译为：
// ① 检查 x 是否为负
// ② 若负，加偏置 (4-1)=3
// ③ 算术右移 2 位

# GCC 编译 int y = x / 4; 的典型输出
movl    %edi, %eax
sarl    $31, %eax       # eax = x 的符号位扩展（全0或全1）
shrl    $30, %eax       # eax = 0（正数）或 3（负数）← 偏置值 2^k - 1
addl    %eax, %edi      # x += 偏置（仅对负数有效）
sarl    $2, %edi        # x >>= 2（算术右移，即 ÷4）

对比：右移除法 vs 真正除法

	正数	负数
逻辑右移 >>	等于 $\lfloor x/2^k \rfloor$（正确）	不适用（无符号无负数）
算术右移 >>	等于 $\lfloor x/2^k \rfloor$（正确）	$\lfloor x/2^k \rfloor$（向负无穷取整，不是 C 的 /）
算术右移 + 偏置	—	$\lceil x/2^k \rceil$（向零取整，等于 C 的 /）

为什么编译器不直接用除法指令？ 因为 div / idiv 指令通常需要 20~40 个时钟周期，而移位 + 加法只需 1~2 个周期。除以 $2$ 的幂时，性能差距可达 20 倍。

---

3.8 整数运算总览

运算	公式	溢出行为	位级等价
$UAdd$	$(u+v) \mod 2^w$	进位丢失，结果变小	与 TAdd 相同
$TAdd$	$U2T((u+v) \mod 2^w)$	正溢出→负，负溢出→正	与 UAdd 相同
$UMult$	$(u \times v) \mod 2^w$	高位截断	与 TMult 相同
$TMult$	$U2T((u \times v) \mod 2^w)$	高位截断	与 UMult 相同
$\times 2^k$	$x \ll k$	同加法溢出	无符号/补码通用
$\div 2^k$（无符号）	$x \gg_L k$（逻辑右移）	无	向零取整
$\div 2^k$（补码）	$(x + \text{bias}) \gg_A k$	无	偏置后向零取整

最重要的一句话：无符号和补码的加法、乘法在位级上完全相同——CPU 用同一组电路完成运算，只在解读结果时才区分有符号/无符号。这就是补码被选为标准编码的根本优势。

---

四、浮点数（Floating Point）

浮点数用于表示实数，现代计算机统一采用 IEEE 754 标准。在了解标准之前，我们需要先直观地理解，计算机是如何用二进制表示小数的。

---

4.1 二进制小数（Fractional Binary Numbers）

在十进制中，小数点左边数字的权重是 $10^0, 10^1, 10^2 \dots$，右边数字的权重是 $10^{-1}, 10^{-2} \dots$。例如：
$12.34_{10} = 1 \times 10^1 + 2 \times 10^0 + 3 \times 10^{-1} + 4 \times 10^{-2}$

二进制小数的原理完全相同，只是权重变成了 $2$ 的幂。小数点左边的权重是 $2^0, 2^1, 2^2 \dots$，右边是 $2^{-1}, 2^{-2} \dots$ 即 $\frac{1}{2}, \frac{1}{4}, \frac{1}{8} \dots$。

直观示例

二进制	权重计算式	十进制值
101.11	$4 + 0 + 1 + \frac{1}{2} + \frac{1}{4}$	$5.75$
0.1	$\frac{1}{2}$	$0.5$
0.01	$\frac{1}{4}$	$0.25$
0.001	$\frac{1}{8}$	$0.125$

关键认知：二进制小数只能精确表示那些分母是 $2$ 的次方的数（比如 $0.5, 0.25, 0.75$ 也就是 $3/4$）。如果遇到像 $0.2$（即 $\frac{1}{5}$）或者 $0.1$（$\frac{1}{10}$）这样的数，无论是用几位二进制去拼凑（如 $\frac{1}{16} + \frac{1}{32} \dots$），都只能通过无限循环去逼近，永远无法绝对精确地表示！这就是为什么在很多语言中 0.1 + 0.2 != 0.3 的根本原因。

---

4.2 IEEE 754 的基本结构：二进制的科学记数法

浮点数的核心可以直接对应到科学记数法，只是从十进制平移到了二进制。

回忆一下熟悉的十进制科学记数法表示法：$-1.23 \times 10^4$

• 负号（-）：决定整个数值的正负。
• 有效数字（1.23）：包含了这一串数字真正的精度和内容。
• 基数（10）：表示我们使用的是逢十进一的进制。
• 指数（4）：决定了这个数值的具体大小量级，它本质上在告诉我们"小数点需要往右浮动几位"。这也是浮点数这个名字的核心。

IEEE 754 其实就是把上述过程平移到了二进制（逢二进一）：

$$V = (-1)^s \times M \times 2^E$$

1. 符号（Sign, $s$）：就像上面的负数标记。
   • 0 代表正数，1 代表负数。这非常稳定地占据了总比特位中最高的 1 位。
2. 阶码（Exponent, $E$）：就像 $10^4$ 里面的 $4$。
   • 决定数值在数轴上的大致位置（它是成万还是微米级别）。
   • 在底层的编码里，这段专门划分出来的存放阶码的区域叫 exp，并且占据了 $k$ 个比特位。
3. 尾数（Significand/Mantissa, $M$）：就像 $1.23$ 里面的 $123$。
   • 决定了数值有多精确。你给出的尾数空间越长，你的数值越不易被模糊化。
   • 在底层的编码里，这就叫 frac，即有效位的存储区，占据剩下的 $n$ 个比特位。

常见精度对应的位宽划分表

面对 32 位或者 64位 的空盘，这三块肉是如何瓜分比特位的？

精度类型	符号位 $s$	阶码 exp	尾数 frac	总位宽
单精度（float）	1 位	8 位	23 位	32 位
双精度（double）	1 位	11 位	52 位	64 位

位段填写模板（S / exp / frac）

手动填写位模式时，可以先画固定模板，再往里填：

单精度（32 位）

字段	位范围（高位到低位）	位数	填写内容
S	bit 31	1	正数填 0，负数填 1
exp	bit 30..23	8	存偏置后的阶码（或全 0 / 全 1 特殊码）
frac	bit 22..0	23	小数部分有效位，不含规格化数的隐含前导 1

位布局（从左到右）：
[ S ][ exp(8) ][ frac(23) ]

双精度（64 位）

字段	位范围（高位到低位）	位数	填写内容
S	bit 63	1	正数填 0，负数填 1
exp	bit 62..52	11	存偏置后的阶码（或全 0 / 全 1 特殊码）
frac	bit 51..0	52	小数部分有效位，不含规格化数的隐含前导 1

位布局（从左到右）：
[ S ][ exp(11) ][ frac(52) ]

填写顺序（统一流程）

1. 先写 S：看正负号。
2. 再写 exp：
   • 规格化数：exp = E + Bias（float 的 Bias=127，double 的 Bias=1023）。
   • 非规格化数：exp 全 0。
   • 无穷/NaN：exp 全 1。
3. 最后写 frac：
   • 规格化数：写 1.xxx... 里的 xxx...。
   • 非规格化数：直接写有效小数位。
   • 无穷：frac 全 0；NaN：frac 非全 0。

这套模板在单精度和双精度都通用，区别只在 exp 与 frac 的位数。

浮点转化固定流程（避免在 exp / E / frac / M 之间打架）

先固定一条总公式：

$$V = (-1)^s \times M \times 2^E$$

再记住各符号只负责一件事：

• exp：存储在位字段里的“编码指数”
• $E$：真实指数（参与公式计算）
• frac：位字段里的小数位串
• $f$：把 frac 当二进制小数解释后的值
• $M$：有效数字（规格化时 $1+f$，非规格化时 $f$）

可以按两个方向做题。

A. 数值 $\to$ IEEE 位模式（编码流程）

1. 定精度（float 或 double），先写好位框：S | exp | frac。
2. 写 S：正数 0，负数 1。
3. 把绝对值写成二进制科学记数法：$1.xxx\times2^E$（若是接近 0 的极小数，要考虑非规格化）。
4. 判分类并写 exp：
   • 规格化：exp = E + Bias
   • 非规格化：exp = 0...0
   • 溢出到无穷：exp = 1...1, frac = 0...0
5. 写 frac：
   • 规格化：写 1.xxx 的 xxx
   • 非规格化：直接写有效小数位
6. 位数不够就按舍入规则处理，最后拼成二进制/十六进制。

B. IEEE 位模式 $\to$ 数值（解码流程）

1. 先拆字段：S、exp、frac。
2. 先看 exp 判分类：
   • exp 全 0：零或非规格化
   • exp 全 1：无穷或 NaN
   • 其他：规格化
3. 分类后再算 $E$ 和 $M$：
   • 规格化：$E=exp-Bias$，$M=1+f$
   • 非规格化：$E=1-Bias$，$M=f$
4. 用 frac 算 $f$（例如 010... 表示 $2^{-2}$）。
5. 代入 $V = (-1)^s \times M \times 2^E$，最后写十进制或分数。

一句话速记：

• 编码：先数值归一化，再填 S/exp/frac。
• 解码：先看 exp 分类，再算 $E/M$ 代公式。

案例实战：将十进制 15.25 转为 IEEE 754 单精度浮点数

纸上得来终觉浅，我们亲自手动推导一次 15.25 是如何变成机器里那 $32$ 个 0 和 1 的：

第一步：转换为二进制
整数部分 $15 = 1111_2$。
小数部分 $0.25 = \frac{1}{4} = 0.01_2$。
拼起来得到：$15.25_{10} = 1111.01_2$。

第二步：变成"二进制科学记数法"
将小数点向左移动 3 位，直到整数部分只剩下一个 1：
$1111.01_2 \to 1.11101_2 \times 2^3$
（此时，你就已经得到了关键参数：指数 $E = 3$，而且它是正数，所以符号 $s = 0$）

第三步：填充 32 位的三个字段

1. 符号位 (1 位)：正数，天上掉下个 0。
2. 阶码 (8 位)：单精度规定的偏置 Bias 为 127。
   • exp 编码值 = 真正的指数 $E$ + Bias = $3 + 127 = 130$。
   • 将 130 转为二进制：10000010。
3. 尾数 (23 位)：取小数点后面的部分 11101（因为最前面的 1. 是所有数都有的，所以 IEEE 规定将其"白嫖"省略掉，不占存储空间）。
   • 将 11101 放入 23 位的头部，后面全部补 0 凑满：11101000000000000000000。

第四步：拼出最终位模式
把这三块肉串起来：0 + 10000010 + 11101000000000000000000
组合成 32 比特：
0100 0001 0111 0100 0000 0000 0000 0000
转成十六进制，就是在内存中真正存下的字节流：0x41740000。

---

4.3 浮点数的三种分类

根据 exp 字段的值，浮点数被分为三种互相排斥的情况：

1. 规格化值（Normalized）

当 exp 既不是全 0，也不是全 1 时，表示规格化值。这是最普遍的情况。

为什么要"规格化"？
任何一个浮点数如果在科学记数法下不加限制，会有无数种表现形式。比如 $15.25$ 可以写成 $15.25 \times 10^0$，也能写成 $1.525 \times 10^1$。为了避免同一个数字在底层出现好几种不同的二进制组合（这会导致比较和计算极其复杂），IEEE 754 强制要求：小数点左边必须且只能是一个非零的数字。

在十进制里，这意味着首位是 $1 \sim 9$；而在二进制的世界里，"非零数字"只有 1 这一种可能！这就带来了一个绝妙的设计，既然所有规格化数都是以 1. 开头，那这个 1 就成了废话，根本不需要被专门存进物理磁盘里！这也就是下文中"隐含的 1"的由来，它让我们在同样的物理位宽里多出了一位数据精度。

• 阶码 $E$：$E = \text{exp} - \text{Bias}$。
  • 其中 $\text{Bias} = 2^{k-1} - 1$。
  • 单精度 $\text{Bias} = 127$，双精度 $\text{Bias} = 1023$。
  • 使用 Bias 而不是补码来表示负指数，目的是为了让浮点数的位模式可以直接用无符号整数的比较器比较大小（阶码在高端，越大的数在无符号解读下也越大）。
• 尾数 $M$：$M = 1 + f$。
  • 其中 $f$ 是 frac 字段解释为小数的值（范围 $0 \le f < 1$）。
  • 隐含的 1：有效数字总是以 1. 开头，所以不需要显式存储这个 1，白嫖了 1 位精度。

2. 非规格化值（Denormalized）

当 exp 为全 0 时，表示非规格化值。主要用来表示 $0$，以及非常接近 $0$ 的极小数值。

• 阶码 $E$：$E = 1 - \text{Bias}$（特殊规定，为了和规格化值平滑衔接）。
• 尾数 $M$：$M = f$（没有隐含的 1）。
• 用途：
  • 当 frac 也是全 0 时，表示 $0$。注意浮点数有 $+0.0$ 和 $-0.0$ 两个零，它们在比较时相等。
  • 逐渐下溢（Gradual underflow）：填补了最小的规格化数和 $0$ 之间的空隙。

3. 特殊值（Special Values）

当 exp 为全 1 时，表示特殊值。

• 无穷大（Infinity, $\pm\infty$）：当 frac 为全 0 时。表示溢出或除以 $0$ 等极其大的结果。
• Not a Number (NaN)：当 frac 非全 0 时。表示未定义的操作结果，例如 $\sqrt{-1}$ 或 $\infty - \infty$。

4.3.1 非规格化数的转化示例（单精度）

目标：把最小正非规格化数写成 IEEE 754 单精度位模式。

已知：

• 单精度 Bias = 127
• 非规格化数规则：exp 全 0，$E = 1 - Bias = -126$，$M = f$（无隐含前导 1）

最小正非规格化数要求 frac 只有最低位是 1：

• S = 0
• exp = 00000000
• frac = 00000000000000000000001

于是：

$$f = 2^{-23},\quad M = 2^{-23},\quad E = -126$$ $$V = (-1)^0 \times M \times 2^E = 2^{-23} \times 2^{-126} = 2^{-149}$$

十进制近似值：

$$V \approx 1.40129846 \times 10^{-45}$$

同理，如果 frac 末两位为 11（其余位为 0），值就是：

$$(2^{-22}+2^{-23})\times2^{-126}=3\times2^{-149}$$

4.3.2 IEEE 位模式还原为十进制小数 / 分数

按统一步骤还原：先拆 S/exp/frac，再判定分类，最后代入

$$V = (-1)^s \times M \times 2^E$$

例 1：0x3FC00000（单精度）

• 二进制：0 01111111 10000000000000000000000
• s=0，exp=127，frac 最高位为 1
• 规格化数：$E=127-127=0$
• $f=2^{-1}$，所以 $M=1+2^{-1}=1.5$

$$V = (+1)\times1.5\times2^0 = 1.5 = \frac{3}{2}$$

例 2：0x3E200000（单精度）

• 二进制：0 01111100 01000000000000000000000
• s=0，exp=124，规格化数
• $E=124-127=-3$
• $f=2^{-2}=0.25$，所以 $M=1.25=\frac{5}{4}$

$$V = (+1)\times\frac{5}{4}\times2^{-3} = \frac{5}{32} = 0.15625$$

上面两个例子分别对应“还原成十进制小数”和“还原成精确分数”的常用写法。

---

4.4 舍入（Rounding）

浮点数只能保留有限位，尾部被截掉时就要决定“进不进 1”。

可以把一个数写成：

保留部分 | 被舍弃部分

记号约定：

• $L$：保留部分的最低位（LSB）
• $G$：被舍弃部分第一位（guard bit）
• $R$：$G$ 之后剩余位是否存在 1（存在则 $R=1$，否则 $R=0$）

判定直觉：

• $G=0$：被舍弃部分小于一半，不进位。
• $G=1, R=1$：超过一半，进位。
• $G=1, R=0$：刚好一半（tie），看舍入模式。

IEEE 四种模式可直接记成下表：

模式	规则	正数效果	负数效果
向偶数舍入（Round-to-Even，默认）	先选最近值；若 tie，则让结果最低位为偶数	有时进位，有时不进位	同左
向零舍入（Toward Zero）	直接截断	变小或不变	绝对值变小或不变
向下舍入（Toward $-\infty$）	取不大于原值的最大可表示数	截断（不进）	可能进位（更负）
向上舍入（Toward $+\infty$）	取不小于原值的最小可表示数	可能进位（更大）	截断（不进）

向偶数舍入的 tie 细则（最常考）

当且仅当 $G=1, R=0$（被舍弃部分是 1000...0）时，属于 tie：

• 若 $L=0$（当前最低位已是偶数），不进位。
• 若 $L=1$（当前最低位是奇数），进位，进到偶数。

这条规则的效果是长期统计更中性，不会像“总是向上”那样积累偏差。

快速例子（按“保留 3 位小数”理解）

• $1.010\underline{011}_2$：$G=0$，不进位，结果 $1.010_2$。
• $1.010\underline{101}_2$：$G=1,R=1$，进位，结果 $1.011_2$。
• $1.010\underline{1000}_2$：tie，且 $L=0$，不进位，结果 $1.010_2$。
• $1.011\underline{1000}_2$：tie，且 $L=1$，进位，结果 $1.100_2$。

十进制类比也一致：

• 向偶数：$1.5\to2$，$2.5\to2$，$3.5\to4$。
• 向零：$-1.9\to-1$。
• 向下：$-1.1\to-2$。
• 向上：$-1.1\to-1$。

---

4.5 浮点运算的陷阱

由于精度的固有限制，浮点数运算与数学上的实数运算有本质区别。

1. 缺乏结合律

(3.14 + 1e20) - 1e20  // 结果为 0.0！(3.14 被 1e20 吸收了精度)
3.14 + (1e20 - 1e20)  // 结果为 3.14

启示：编译器通常不敢对浮点运算进行重排序优化，因为顺序会改变结果。

2. 缺乏分配律
$a \times (b + c)$ 不一定等于 $(a \times b) + (a \times c)$。

3. C 语言中的数据类型转换

转换	是否丢失精度	说明
int $\to$ float	可能会丢失精度	单精度尾数仅 23 位，表示不完全 32 位的整型信息
int $\to$ double	安全且精确	双精度尾数有 52 位，足以装下整个 32 位 int
float $\to$ double	安全且精确	完全被包容
double $\to$ float	可能溢出 ($\pm\infty$)，可能舍入
float / double $\to$ int	向零舍入	如果浮点数值超过 int 上限，C 语言不保证结果（通常会变成 INT_MIN 作为惩罚）

关键认知：浮点数可以表示极大的范围，但它在连续实数轴上的分布是极度不均匀的。越接近原点（数值越小），刻度越密，精度极高；到了 $10^{10}$ 以上，相邻两个浮点数之间的跨度可能比 $1000$ 还要大。实际代码中通常不直接用 == 比较两个浮点数是否相等，而是比较它们的差值绝对值是否小于阈值 $\epsilon$。

---

4.6 浮点数表示范围（速查）

设 exp 位数为 $k$，frac 位数为 $n$，Bias 为 $2^{k-1}-1$。

• 最大真实指数：$E_{max} = (2^k - 2) - Bias$
• 最小规格化指数：$E_{min} = 1 - Bias$
• 最大规格化值：$(2 - 2^{-n}) \times 2^{E_{max}}$
• 最小规格化正值：$2^{E_{min}}$
• 最小非规格化正值：$2^{E_{min}-n}$

对应到 IEEE 754 常见类型：

类型	Bias	指数范围（规格化）	最大有限值	最小规格化正值	最小非规格化正值
float（32 位）	127	$-126 \sim +127$	$3.4028235\times10^{38}$	$1.17549435\times10^{-38}$	$1.40129846\times10^{-45}$
double（64 位）	1023	$-1022 \sim +1023$	$1.7976931348623157\times10^{308}$	$2.2250738585072014\times10^{-308}$	$4.9406564584124654\times10^{-324}$

补充：

• 负数范围与正数对称（除去符号位影响）。
• exp 全 1 且 frac 全 0 表示 $\pm\infty$，因此它们不属于“最大有限值”。
• 0 附近最小间隔不是固定值，而是随数量级变化；越靠近 0，间隔越小。

---

4.7 8bit 课堂模型：非规格化到规格化（1/4/3）

按课堂演示模型，位宽划分为：S=1，exp=4，frac=3。

• 指数位数 $k=4$，尾数位数 $n=3$
• Bias $=2^{k-1}-1=7$
• 下面只列正数（S=0），负数对称
• “跨度”指相邻可表示数之间的差值（ULP）

非规格化区（exp=0000）

此时：$E=1-Bias=-6$，$M=f=\frac{frac}{2^3}$，所以

$$value = f\times 2^E = \frac{frac}{8}\times2^{-6}=frac\times2^{-9}$$

位模式（S exp frac）	$E$	value（分数）	value（十进制）	跨度到下一个
0 0000 001	$-6$	$2^{-9}$	0.001953125	$2^{-9}$
0 0000 010	$-6$	$2\times2^{-9}$	0.00390625	$2^{-9}$
0 0000 011	$-6$	$3\times2^{-9}$	0.005859375	$2^{-9}$
0 0000 100	$-6$	$4\times2^{-9}$	0.0078125	$2^{-9}$
0 0000 101	$-6$	$5\times2^{-9}$	0.009765625	$2^{-9}$
0 0000 110	$-6$	$6\times2^{-9}$	0.01171875	$2^{-9}$
0 0000 111（最大非规）	$-6$	$7\times2^{-9}$	0.013671875	$2^{-9}$（到最小规）

过渡点（非规格化 $\to$ 规格化）

项	位模式（S exp frac）	$E$	value
最大非规格化正数	0 0000 111	$-6$	$7\times2^{-9}$
最小规格化正数	0 0001 000	$-6$	$1\times2^{-6}=8\times2^{-9}$

两者差值：$8\times2^{-9}-7\times2^{-9}=2^{-9}$，所以过渡处没有断层，间距连续。

规格化区（exp=0001 到 1110）

此时：$E=exp-Bias$，$M=1+\frac{frac}{8}$，固定某个 $E$ 时

$$value\in[1.000_2\times2^E,\ 1.111_2\times2^E]=[2^E,\ (2-2^{-3})2^E]$$

且该区间内跨度为：

$$\Delta = 2^{E-3}$$

exp	$E$	value 范围（正数）	跨度 $\Delta$
0001	$-6$	$[2^{-6},\ 1.875\times2^{-6}]$	$2^{-9}$
0010	$-5$	$[2^{-5},\ 1.875\times2^{-5}]$	$2^{-8}$
0011	$-4$	$[2^{-4},\ 1.875\times2^{-4}]$	$2^{-7}$
0100	$-3$	$[2^{-3},\ 1.875\times2^{-3}]$	$2^{-6}$
0101	$-2$	$[2^{-2},\ 1.875\times2^{-2}]$	$2^{-5}$
0110	$-1$	$[2^{-1},\ 1.875\times2^{-1}]$	$2^{-4}$
0111	$0$	$[1,\ 1.875]$	$2^{-3}$
1000	$1$	$[2,\ 3.75]$	$2^{-2}$
1001	$2$	$[4,\ 7.5]$	$2^{-1}$
1010	$3$	$[8,\ 15]$	$2^0$
1011	$4$	$[16,\ 30]$	$2^1$
1100	$5$	$[32,\ 60]$	$2^2$
1101	$6$	$[64,\ 120]$	$2^3$
1110	$7$	$[128,\ 240]$	$2^4$

观察：从 $E=-6$ 往上，每升高 1 档指数，跨度翻倍。这也是“数越大，刻度越稀”的直接来源。

---

4.8 浮点数加法

4.8.1 固定流程

1. 拆成 $(-1)^s, M, E$（先判规格化/非规格化）。
2. 处理特殊值：NaN、$\pm\infty$ 先行返回。
3. 对阶：把较小指数的尾数右移，直到两个数指数相同。
4. 按符号做尾数加减（同号相加，异号相减）。
5. 结果规格化：
   • 若尾数 $\ge 2$，右移一位并 $E+1$
   • 若尾数 $<1$（且非 0），左移并 $E-1$
6. 舍入到目标位数（按当前舍入模式，默认向偶数）。
7. 检查溢出/下溢，最后回填 S | exp | frac。

例（8bit 模型：S=1, exp=4, frac=3）

计算：0 0101 000 + 0 0100 100

• A：0 0101 000，$E=5-7=-2$，$M=1.000_2$，值 $=1.000_2\times2^{-2}=0.25$
• B：0 0100 100，$E=4-7=-3$，$M=1.100_2$，值 $=1.100_2\times2^{-3}=0.1875$

对阶到 $E=-2$：

$$1.100_2\times2^{-3}=0.110_2\times2^{-2}$$

尾数相加：

$$1.000_2+0.110_2=1.110_2$$

结果已规格化，不需再移位：

$$1.110_2\times2^{-2}=0.4375$$

回填：$S=0, E=-2\Rightarrow exp=5=0101, frac=110$，结果位模式：

$$\boxed{0\ 0101\ 110}$$

4.8.2 加法易错点

• 忘记先对阶，直接把尾数相加。
• 异号相加本质是尾数相减，结果可能需要左规（左移并减指数）。
• 规格化后指数变化了，但 exp 没重算。

---

4.9 浮点数乘法

4.9.1 固定流程

1. 拆成 $(-1)^s, M, E$。
2. 处理特殊值：NaN、$0\times\infty$、$\infty\times$ 非 0 等。
3. 符号位：$s=s_1\oplus s_2$。
4. 指数相加：$E=E_1+E_2$。
5. 尾数相乘：$M=M_1\times M_2$。
6. 结果规格化（若 $M\ge2$ 则右移并 $E+1$）。
7. 舍入、检查溢出/下溢、回填 S | exp | frac。

例（8bit 模型：S=1, exp=4, frac=3）

计算：0 0110 010 × 0 0111 100

• A：$E=6-7=-1$，$M=1.010_2=1.25$
• B：$E=7-7=0$，$M=1.100_2=1.5$

符号：$0\oplus0=0$

指数：

$$E=-1+0=-1$$

尾数：

$$M=1.010_2\times1.100_2=1.111_2=1.875$$

已规格化，回填：$exp=E+Bias=-1+7=6=0110$，$frac=111$，结果位模式：

$$\boxed{0\ 0110\ 111}$$

十进制校验：$0.625\times1.5=0.9375$，与结果一致。

4.9.2 乘法易错点

• 乘法后忘记再规格化（尤其尾数乘积落到 $[2,4)$）。
• 指数相加后没考虑规格化再 +1，导致最终 exp 偏小 1。
• 只算了符号和指数，漏掉舍入步骤。

---

4.10 浮点加法/乘法的数学特性

设浮点加法、乘法分别记为 $\oplus$、$\otimes$（表示“先按实数算，再舍入到目标格式”）。

4.10.1 只看浮点加法 $\oplus$

通常成立：

• 加法交换律：$x\oplus y = y\oplus x$
• 加法单位元：$x\oplus 0 = x$

常失效：

• 加法结合律通常不成立：$(x\oplus y)\oplus z \neq x\oplus(y\oplus z)$
• 加法消去律不可靠：$x\oplus a = y\oplus a$ 不一定推出 $x=y$

反例（加法结合律）：

• $(3.14 + 1e20) - 1e20 = 0$
• $3.14 + (1e20 - 1e20) = 3.14$

原因是“对阶 + 舍入”会把小量吞掉，改变中间结果。

4.10.2 只看浮点乘法 $\otimes$

通常成立：

• 乘法交换律：$x\otimes y = y\otimes x$
• 乘法单位元：$x\otimes 1 = x$
• 符号规律：$(-x)\otimes y = -(x\otimes y)$

常失效：

• 乘法结合律在有限精度下也可能失效：$(x\otimes y)\otimes z \neq x\otimes(y\otimes z)$
  • 直觉：两边的舍入发生在不同步骤，中间误差不同。

4.10.3 加法与乘法混合

常失效：

• 分配律通常不成立：

$$x\otimes(y\oplus z) \neq (x\otimes y)\oplus(x\otimes z)$$

常见场景：$y\approx -z$ 且数量级大时，$y\oplus z$ 先发生严重抵消，再乘 $x$，结果与“先乘后加”不同。

结论（做题口令）：

• 看见纯加法变形，先警惕“加法结合律/消去律”。
• 看见纯乘法变形，先警惕“乘法结合律”。
• 看见加乘混合变形，先警惕“分配律”。