第 3 章计算机算术 (Arithmetic for Computers)

核心结论

整数加减法：二进制加法器串行进位；溢出靠符号位进位与最高位进位的异或检测。
整数乘法：移位-加法器（Shift-and-Add）；LEGv8 MUL / MULH（高低位分开）。
整数除法：恢复余数 / 非恢复余数除法器；LEGv8 SDIV / UDIV。
IEEE 754 浮点：符号 + 指数 + 尾数；规格化数 / 非规格化数 / NaN / 无穷；舍入模式（最近偶数 / 朝 0 / 朝 +∞ / 朝 -∞）。
SIMD 与并行：一条指令处理多个数据（ARM NEON / SSE / AVX）；提升 4-16 倍吞吐。
子字并行：把 32-bit 寄存器拆为 4 个 8-bit / 2 个 16-bit 同时运算；GPU / ML 常用。

本章主旨

本章聚焦"ALU 怎么做算术"——整数加减乘除、IEEE 754 浮点、SIMD / 子字并行。这些是 CPU 微架构的核心电路，与第 4 章的 CPU 设计直接挂钩。理解算术电路有助于理解延迟 / 吞吐量 / 优化的硬件根源。

一、核心概念

本章围绕 6 个核心概念展开：从整数加法出发，介绍乘法 / 除法的移位-加法实现，再深入 IEEE 754 浮点，最后给 SIMD 与子字并行。

概念定义 + 重要性实现提示

概念	定义 + 重要性	实现提示
整数加减法	二进制加法器串行进位；溢出靠符号位与最高位的进位异或检测。	§3.2；超前进位加速但复杂；现代 ALU 用超前进位 + 串行进位混合。
整数乘法	移位-加法（Shift-and-Add）；LEGv8 `MUL`（低 64-bit）+ `MULH`（高 64-bit）。	§3.3；64-bit × 64-bit 结果 128-bit，分两次取；迭代次数 = 操作数位数。
整数除法	恢复 / 非恢复余数除法；LEGv8 `SDIV` / `UDIV`（硬件实现，几十个周期）。	§3.4；除法比乘法慢（迭代 + 比较 + 减法）；编译器优化：常量除法转乘法 + 移位。
IEEE 754 浮点	符号 (1) + 指数 (8/11) + 尾数 (23/52)；规格化 / 非规格化 / NaN / 无穷；4 种舍入。	§3.5；高精度计算的基础；浮点不精确（`0.1 + 0.2 ≠ 0.3`）。
SIMD 与并行	一条指令处理多个数据；ARM NEON、x86 SSE / AVX；4-16 倍吞吐。	§3.6-§3.7；GPU / 矩阵运算 / 图像处理的标准优化。
子字并行 (subword parallelism)	把宽寄存器拆为多个窄数据并行运算；ML / 图像 / 加密常用。	§3.9；ARM SVE / AVX-512 把 SIMD 推到极致。

整数加减法

二进制加法器串行进位；溢出靠符号位与最高位的进位异或检测。

§3.2；超前进位加速但复杂；现代 ALU 用超前进位 + 串行进位混合。

整数乘法

移位-加法（Shift-and-Add）；LEGv8 MUL（低 64-bit）+ MULH（高 64-bit）。

§3.3；64-bit × 64-bit 结果 128-bit，分两次取；迭代次数 = 操作数位数。

整数除法

恢复 / 非恢复余数除法；LEGv8 SDIV / UDIV（硬件实现，几十个周期）。

§3.4；除法比乘法慢（迭代 + 比较 + 减法）；编译器优化：常量除法转乘法 + 移位。

IEEE 754 浮点

符号 (1) + 指数 (8/11) + 尾数 (23/52)；规格化 / 非规格化 / NaN / 无穷；4 种舍入。

§3.5；高精度计算的基础；浮点不精确（0.1 + 0.2 ≠ 0.3）。

SIMD 与并行

一条指令处理多个数据；ARM NEON、x86 SSE / AVX；4-16 倍吞吐。

§3.6-§3.7；GPU / 矩阵运算 / 图像处理的标准优化。

子字并行 (subword parallelism)

把宽寄存器拆为多个窄数据并行运算；ML / 图像 / 加密常用。

§3.9；ARM SVE / AVX-512 把 SIMD 推到极致。

二、详细笔记

2.1 整数加减法 (Integer Add/Subtract)

What：二进制加法器串行进位；溢出靠符号位进位与最高位进位的异或检测。

Why：加法是 ALU 最基本操作；溢出检测是安全编程的核心。

How：

二进制加法：

\[a + b = \sum_i (a_i \oplus b_i \oplus c_i) \cdot 2^i \end{bmatrix>\]

其中 c_i 是进位，c₀ = 0。

溢出检测（§3.2）：

\[\text{Overflow} = c_{n-1} \oplus c_n \end{bmatrix>\]

两个正数相加得负数、或两个负数相加得正数 = 溢出。

进位加速

串行进位：O(n) 延迟（n 是位数）。
超前进位（Carry-Lookahead, CLA）：O(log n) 延迟；硬件复杂。
现代 ALU 用混合方案（CLA + 串行）平衡速度与复杂度。

When：写汇编 / C 时理解溢出行为；debug 算术 bug；选 int vs long long。

Example：INT_MAX + 1 在 C 中是 未定义行为；现代编译器不会自动 wrap-around。

2.2 整数乘法 (Integer Multiplication)

What：移位-加法（Shift-and-Add）；64-bit × 64-bit = 128-bit，结果分高 / 低位。

Why：乘法是科学计算 / 图形 / ML 的核心；MUL/MULH 指令支持全精度乘法。

How：

移位-加法（§3.3）：

\[\text{result} = \sum_{i=0}^{n-1} (b_i \cdot 2^i) \cdot a = \text{shift-and-add} \end{bmatrix>\]

迭代 n 次（n = 64），每次判断 b_i 并选择加 a·2^i。

LEGv8：

MUL X1, X2, X3：低 64-bit 结果。
MULH X1, X2, X3：高 64-bit 结果（用于 128-bit 乘法）。

乘法加速

简单实现：迭代 n 次（64 次）= 64 个周期。
Booth 编码：减少迭代次数（处理连续 0 / 1）。
Wallace / Dadda 树：硬件并行加速（牺牲面积换速度）。
现代 CPU：3-5 个周期出结果。

When：高性能计算；编译器优化（常量乘法转移位-加法）；ML / 图形矩阵乘法。

Example：X1 * X2 用 MUL 取低 64 位；X1 * X2 完整结果 = (MULH << 64) | MUL。

2.3 整数除法 (Integer Division)

What：恢复余数 / 非恢复余数除法；迭代次数 = 操作数位数。

Why：除法是科学计算常用；现代 CPU 几十个周期出结果。

How：

恢复余数除法（§3.4）：迭代 n 次，每次左移余数并比较除数；若余数 < 除数恢复，否则商位 = 1。

非恢复余数除法：迭代 n 次，根据上一步符号决定加 / 减除数；最后修正余数符号。

LEGv8：

SDIV X1, X2, X3：有符号除法。
UDIV X1, X2, X3：无符号除法。

除法优化

编译器把 常量除法 转 乘法 + 移位：例如 x / 5 约等于 x * 0x6666666666666667 >> 65（高位乘法）。
现代 CPU：SDIV / UDIV 通常 10-20 个周期。

When：编译器优化（除法 → 乘法）；硬件除法器设计；理解延迟。

Example：UDIV X1, X2, #5（除以 5 无符号）— 编译器转 MUL X1, X2, #0xCCCCCCCD; LSR X1, X1, #38。

2.4 IEEE 754 浮点 (IEEE 754 Floating Point)

What：符号 + 指数 + 尾数；规格化 / 非规格化 / NaN / 无穷；4 种舍入模式。

Why：浮点是科学计算 / 图形 / ML 的标准；IEEE 754 保证跨平台一致性。

How：

二进制表示（§3.5）：

\[(-1)^s \times 1.\text{fraction} \times 2^{\text{exponent} - \text{bias}} \end{bmatrix>\]

s：1 bit 符号。
exponent：8 bit (单精度) / 11 bit (双精度)。
fraction：23 bit (单精度) / 52 bit (双精度)；规格化时隐含 1。
bias：127 (单) / 1023 (双)。

特殊值：

全 0 指数 + 全 0 尾数 = ±0。
全 1 指数 + 全 0 尾数 = ±∞。
全 1 指数 + 非 0 尾数 = NaN。
全 0 指数 + 非 0 尾数 = 非规格化数（指数 = -126 / -1022）。

IEEE 754 的"反直觉"特性

0.1 + 0.2 ≠ 0.3：因为 0.1 / 0.2 / 0.3 都不能精确二进制表示。
1e40 * 1e-40 ≠ 1.0：尾数精度限制；差距过大时丢失小数部分。
x == x 永远 true，除非 x = NaN（用 isnan(x) 检测）。
浮点比较用容差 fabs(a - b) < epsilon 而非 ==。

When：所有科学计算；图形 / 物理引擎；ML 训练；debug 数值 bug。

Example：double d = 0.1 + 0.2; 结果约 0.30000000000000004（不是 0.3）。

2.5 SIMD 与子字并行 (SIMD & Subword Parallelism)

What：一条指令处理多个数据；ARM NEON 128-bit / x86 AVX 256-bit。

Why：图像处理 / 矩阵运算 / ML 大量使用 SIMD；性能提升 4-16 倍。

How：

SIMD 模型（§3.7）：

标量指令：1 条指令处理 1 个数据。
SIMD 指令：1 条指令处理 N 个数据（如 4 个 float / 8 个 int16）。

ARM NEON：

128-bit 寄存器 V0–V31。
一条指令同时处理 4 个 float / 8 个 int32 / 16 个 int16 / 32 个 int8。

子字并行（§3.9）：把宽寄存器拆为多个窄数据并行运算（4×8bit / 2×16bit / …）。

SIMD 的工程优势

单条指令 4-16 倍吞吐。
SIMD 寄存器不破坏标量代码（独立寄存器文件）。
编译器自动向量化（如 GCC -O3 -ftree-vectorize）。
GPU 本质上是 SIMD + 多线程的极端。

When：图形 / 物理 / ML / 加密 / 信号处理；编译器优化（向量化）；手写 SIMD intrinsic。

Example：float a[4], b[4], c[4]; for (i=0; i<4; i++) c[i] = a[i] + b[i]; 可用 1 条 NEON 指令 VADD.F32 Q0, Q0, Q1。

三、关键图表

视觉图表

Figure 1. 图 3-1：1-bit 全加法器

Figure 2. 图 3-2：串行 32-bit 加法器

Figure 3. 图 3-3：超前进位加法器

Figure 4. 图 3-4：移位-加法乘法器

Figure 5. 图 3-5：恢复余数除法器

Figure 6. 图 3-6：IEEE 754 单精度格式

Figure 7. 图 3-7：IEEE 754 浮点范围（规格化 / 非规格化）

Figure 8. 图 3-8：SIMD 寄存器布局

非可视化条目

非可视化条目（表 / 算法）

编号

内容摘要

表 3.1

IEEE 754 单精度 / 双精度格式对比。

表 3.2

LEGv8 算术指令（MUL / SDIV / UDIV / FABSS / FADDS / …）。

式 3-1 至 3-12

补码算术、溢出检测、IEEE 754 编码 / 解码、舍入。

列表 3.1-3.x

LEGv8 整数 / 浮点汇编示例（factorial / 浮点求和）。

表 3.3

ARM NEON / x86 SSE / AVX 对比（寄存器宽度 / 指令数 / 吞吐量）。

核心公式对照表

概念

公式

整数加法（溢出检测）

\(\text{Overflow} = c_{n-1} \oplus c_n\)

IEEE 754 单精度

\((-1)^s \times 1.f \times 2^{e-127}\)

IEEE 754 双精度

\((-1)^s \times 1.f \times 2^{e-1023}\)

单精度范围

\(\pm (2 - 2^{-23}) \times 2^{127} \approx \pm 3.4 \times 10^{38}\)

双精度范围

\(\pm (2 - 2^{-52}) \times 2^{1023} \approx \pm 1.8 \times 10^{308}\)

浮点精度（单位 ulp）

\(\text{ulp} = 2^{e - p}\)，p = 精度位数（23/52）

四、思维导图

mindmap
  root((第 3 章 计算机算术))
    整数加减
      二进制加法器
      进位链
      溢出检测
    整数乘法
      移位加法
      MUL与MULH
      64次迭代
    整数除法
      恢复余数
      SDIVUDIV
      常量优化
    浮点
      IEEE754
      符号指数尾数
      舍入模式
    SIMD
      一指令多数据
      NEONAVX
      4到16倍
    子字并行
      宽拆窄
      ML加密
      SVEAVX512

五、重点与易错点

整数溢出是 C 未定义行为：编译器可优化掉溢出检查；用 __builtin_add_overflow 或 safe-int 库。
- 二进制补码的范围不对称：INT64_MIN = -2^63，其相反数 2^63 超出范围；比较时区分有符号 / 无符号。
- IEEE 754 浮点不精确：0.1 + 0.2 ≠ 0.3；比较用容差 fabs(a-b) < epsilon。
- NaN 不等于自己：检测用 isnan(x)，而非 x == x（虽然 x != x 也 work）。
- 除法比乘法慢：编译器把常量除法转乘法 + 移位；硬件除法器用 10-20 周期。
- SIMD 是性能倍增器：图像 / 物理 / ML 大量使用；编译器 -O3 -ftree-vectorize 自动向量化。
- ARM NEON 128-bit / x86 AVX 256-bit：寄存器宽度决定并行度；新一代指令集扩展越来越大。
- 子字并行：把宽寄存器拆为窄数据；适合 ML / 加密等小数据并行场景。
- 跨章衔接：第 4 章 CPU 微架构实现本章算术电路；第 5 章内存层级加速浮点数组访问；第 6 章 SIMD + 多线程组合提升并行。

第 3 章 计算机算术 (Arithmetic for Computers)

核心结论

一、核心概念

二、详细笔记

2.1 整数加减法 (Integer Add/Subtract)

2.2 整数乘法 (Integer Multiplication)

2.3 整数除法 (Integer Division)

2.4 IEEE 754 浮点 (IEEE 754 Floating Point)

2.5 SIMD 与子字并行 (SIMD & Subword Parallelism)

三、关键图表

视觉图表

非可视化条目

核心公式对照表

四、思维导图

五、重点与易错点

第 3 章计算机算术 (Arithmetic for Computers)