第3章计算机的算术运算（硬件计算） Arithmetic for Computers

一、导读

1.1 本章学习目标

掌握整数加法和减法的硬件实现：理解半加器、全加器的逻辑设计，掌握行波进位加法器和超前进位加法器（Carry Lookahead Adder）的工作原理，理解补码表示法如何统一加法和减法运算。

理解整数乘法的硬件算法：掌握基本的移位-加法乘法算法，了解 Booth 编码和修正 Booth 算法如何减少部分积数量，理解阵列乘法器和 Wallace 树结构的设计思想。

掌握整数除法的硬件实现：理解恢复余数除法和不恢复余数除法的算法流程，了解 SRT 除法等高级除法算法的基本思想。

深入理解 IEEE 754 浮点数标准：掌握单精度（32 位）和双精度（64 位）浮点数的表示格式，理解规格化数、非规格化数、无穷大和 NaN 的编码规则，能够计算浮点数的表示范围和精度。

掌握浮点数运算的特殊问题：理解浮点数加减法中的对阶、尾数运算和规格化过程，认识浮点运算中的精度损失、溢出和下溢问题，了解 Guard、Round 和 Sticky 位在舍入中的作用。

理解 SIMD 在算术运算中的应用：了解如何通过 SIMD 指令（如 RISC-V 的向量扩展）同时执行多个算术运算，提升数据密集型计算的性能。

能够分析数值计算的精度问题：掌握浮点数精度损失的根本原因，学会预测和避免常见的数值陷阱（如大数吃小数、灾难性抵消等）。

1.2 为什么本章如此重要

算术运算是计算机最基础的功能，所有复杂的计算最终都要归结为基本的加减乘除操作。算术单元的设计直接影响处理器的性能、面积和功耗。ALU（算术逻辑单元）是处理器数据通路的核心组件，其速度和效率决定了关键路径的延迟。

浮点数运算在现代计算中无处不在。科学计算、图形渲染、机器学习、金融分析等领域都高度依赖浮点运算。然而，浮点数的有限精度带来了一系列微妙的问题：0.1 + 0.2 在计算机中并不严格等于 0.3；两个相近数相减可能导致有效数字大量丧失（灾难性抵消）；累加大量小数时可能因为大数吃小数而丢失精度。这些问题不是 bug，而是浮点数表示的固有特性。理解这些特性对于编写正确的数值计算程序至关重要。

从硬件设计的角度看，算术运算的实现方式体现了速度与面积的永恒权衡。行波进位加法器面积小但速度慢（延迟与位数成线性关系），超前进位加法器速度快但面积大（需要额外的进位生成和传播逻辑）。乘法器的设计更加复杂，从简单的移位-加法到复杂的 Booth 编码和 Wallace 树压缩，每种方案在速度、面积和功耗方面都有不同的权衡。

1.3 核心问题引导

为什么计算机使用补码而非原码表示有符号整数？补码在硬件实现上有什么优势？

一个 32 位行波进位加法器的关键路径延迟是多少？如果位数翻倍到 64 位，延迟如何变化？

为什么超前进位加法器不能无限扩展？在实际处理器中如何解决这一问题？

Booth 编码如何将乘法的部分积数量减少一半？其核心思想是什么？

IEEE 754 为什么要引入非规格化数（denormalized numbers）？它们解决了什么问题？

为什么 0.1 + 0.2 != 0.3 在浮点运算中成立？如何在程序中正确处理浮点数比较？

浮点数加法中的"对阶"操作为什么会导致精度损失？如何最小化这种损失？

二、核心概念详解

2.1 整数加法器：从半加器到超前进位

加法是所有算术运算的基础。半加器（Half Adder）是最基本的加法单元，它接收两个 1 位输入 A 和 B，产生和（Sum = A XOR B）与进位（Carry = A AND B）。全加器（Full Adder）在半加器的基础上增加了进位输入 Cin，输出 Sum = A XOR B XOR Cin 和 Cout = (A AND B) OR (Cin AND (A XOR B))。

行波进位加法器（Ripple Carry Adder）将 N 个全加器串联，低位的进位输出连接到高位的进位输入。其关键路径延迟为 N * t_FA（t_FA 为单个全加器的延迟），即延迟与位数成线性关系。对于 32 位加法器，最坏情况下进位需要从最低位传播到最高位，经过 32 个全加器的延迟。

超前进位加法器（Carry Lookahead Adder, CLA）通过并行计算进位信号来加速加法运算。定义进位生成信号 G_i = A_i AND B_i 和进位传播信号 P_i = A_i XOR B_i，则第 i 位的进位可以表示为：

C_i = G_i OR (P_i AND C_{i-1})
    = G_i OR (P_i AND G_{i-1}) OR (P_i AND P_{i-1} AND G_{i-2}) OR ...

通过展开递推关系，可以在常数时间内计算所有进位（理论上），但所需的逻辑门数量随位数指数增长。实际设计中通常采用分组策略：在组内使用超前进位，组间使用行波进位（如 4 位 CLA 级联），或者使用多级超前进位（如 16 位 CLA 由 4 个 4 位 CLA 组成）。

2.2 整数乘法：从移位加法到 Booth 算法

无符号整数乘法的基本思想与手算乘法相同：对于乘数的每一位，如果被乘位为 1，则写下被乘数（左移相应位数），否则写下 0；最后将所有部分积相加。

移位-加法乘法器的实现非常简单：使用一个移位寄存器和一个加法器。每一步检查乘数最低位，如果为 1 则将被乘数加到部分积中，然后将被乘数左移一位、乘数右移一位。N 位乘法需要 N 步完成。

Booth 算法通过编码技巧减少部分积的数量。基本 Booth 算法（Radix-2）检查乘数相邻两位的差值：00 或 11 表示部分积为 0，01 表示加被乘数，10 表示减被乘数。这样可以将连续为 1 的乘数位转化为一次减法和一次加法，显著减少操作次数。

修正 Booth 算法（Modified Booth / Radix-4）每次检查三位，将 N 位乘法减少为 N/2 个部分积。这直接减少了需要相加的部分积数量，从而减少了加法器阵列的级数和总延迟。现代处理器通常使用更高基数的 Booth 编码（如 Radix-8，每次检查四位，产生 N/3 个部分积）。

Wallace 树用于高效地将多个部分积压缩为两个（一个和向量、一个进位向量），然后用一个快速加法器得到最终结果。Wallace 树使用全加器和半加器将每三个部分积减少为两个，每级减少 2/3 的部分积数量，总级数为 log_{3/2}(N)。

2.3 IEEE 754 浮点数表示

IEEE 754 标准定义了浮点数的统一表示格式，解决了不同计算机厂商使用不同浮点格式导致的兼容性问题。

单精度（32 位）格式：1 位符号位 S + 8 位指数位 E + 23 位尾数位 M。实际值为 (-1)^S 1.M 2^(E-127)。指数偏移量为 127，指数范围 1-254 对应实际指数 -126 到 +127。

双精度（64 位）格式：1 位符号位 S + 11 位指数位 E + 52 位尾数位 M。实际值为 (-1)^S 1.M 2^(E-1023)。指数偏移量为 1023。

特殊值的编码：

指数全 0、尾数全 0：表示 +/-0（取决于符号位）
指数全 0、尾数非 0：非规格化数（denormalized number），值 = (-1)^S 0.M 2^(1-bias)，用于渐进下溢（gradual underflow）
指数全 1、尾数全 0：表示 +/-infinity
指数全 1、尾数非 0：表示 NaN（Not a Number），用于表示无效运算结果（如 0/0、sqrt(-1)）

非规格化数的引入填补了最小规格化数和零之间的空隙，使得浮点数的表示在零附近更加均匀，避免了"突然下溢"（sudden underflow）导致的小数直接变为零的问题。

2.4 浮点数加减法运算

浮点数加法比整数加法复杂得多，因为两个操作数的指数可能不同，需要先进行对阶操作。

浮点加法步骤：

对阶：比较两个操作数的指数，将较小指数的操作数的尾数右移，使其指数与较大指数对齐。右移过程中移出的位需要保留（使用 Guard、Round、Sticky 位）以提高精度。

尾数加减：对阶后的尾数进行加法或减法运算（根据操作符号和两数大小关系决定）。

规格化：将结果规格化（左移或右移尾数并调整指数），确保尾数最高位为 1（规格化数）。

舍入：根据 IEEE 754 定义的舍入模式（默认为"就近舍入到偶数"），使用 Guard、Round、Sticky 位确定舍入方向。

溢出/下溢检查：检查指数是否超出表示范围。

Guard、Round、Sticky 位的作用：在对阶右移和规格化左移过程中，需要保留超出尾数位数的额外信息。Guard 位是尾数右侧第一位，Round 位是第二位，Sticky 位是之后所有位的逻辑或。这三个位足以实现 IEEE 754 定义的所有四种舍入模式。

2.5 整数除法的硬件实现

除法是所有基本算术运算中最复杂的。基本的恢复余数除法（Restoring Division）算法如下：

初始化：余数 R = 被除数，商 Q = 0
对于 i = N-1 到 0：
    R = R - 除数 * 2^i
    if R >= 0:
        Q[i] = 1
    else:
        Q[i] = 0
        R = R + 除数 * 2^i  // 恢复余数

不恢复余数除法（Non-Restoring Division）通过允许余数为负值来避免恢复步骤，减少了操作次数。SRT 除法则通过冗余商数字集（如 {-1, 0, 1}）进一步加速，允许在某些步骤中跳过操作。

三、深入分析与讨论

3.1 补码表示法的精妙设计

补码表示法是有符号整数在计算机中的标准表示方式，其设计蕴含了深刻的数学原理。在 N 位补码系统中，数值范围为 -2^(N-1) 到 2^(N-1)-1。补码的核心优势在于：零有唯一表示（全 0），加法和减法可以使用相同的硬件电路（减法通过加补码实现），最高位的进位可以直接丢弃。

从数学角度看，补码本质上是模运算。N 位二进制数的模为 2^N，负数 -X 的补码表示等于 2^N - X。当两个补码数相加时，如果结果超出范围，溢出的高位自然被丢弃，等价于对模取余，结果恰好是正确的。这种优雅的数学性质使得补码成为硬件实现的理想选择。

3.2 浮点数精度的本质限制

浮点数的精度限制源于有限的尾数位数。单精度浮点数有 24 位有效数字（23 位尾数 + 1 位隐含位），约等价于十进制的 7.2 位有效数字。这意味着超过 7 位有效数字的计算必然引入舍入误差。

常见的精度陷阱包括：

大数吃小数：当两个数量级差异很大的浮点数相加时，较小数的有效位可能在对阶过程中完全丢失。例如 1e8 + 1.0 在单精度下结果仍为 1e8。
灾难性抵消：两个相近的浮点数相减时，高位有效数字相互抵消，剩余的低位数字包含大量舍入误差，导致结果的相对误差急剧放大。
累加误差：大量浮点数累加时，舍入误差逐步积累。使用 Kahan 求和算法可以显著减少累加误差。

3.3 算术单元的性能优化策略

现代处理器中的算术单元采用了多种优化策略来平衡速度和面积。在加法器方面，前缀加法器（Prefix Adder）如 Kogge-Stone 和 Brent-Kung 提供了不同的速度-面积权衡。Kogge-Stone 加法器速度最快但面积最大（O(N log N) 个门），Brent-Kung 加法器面积较小但级数较多。

乘法器方面，现代设计通常结合 Booth 编码（减少部分积）和 4-2 压缩器（高效压缩部分积），最终使用超前进位加法器完成最终求和。对于大规模乘法（如 64 位），还可能使用 Karatsuba 算法将 O(N²) 的复杂度降低到 O(N¹·⁵⁸⁵)。

四、实践案例

4.1 案例一：浮点数精度导致的 Patriot 导弹故障

1991 年 2 月 25 日，美国 Patriot 导弹防御系统在沙特达兰的失败导致 28 名士兵死亡。事故的根本原因是浮点数精度问题：系统使用 24 位定点数（等效精度约等于单精度浮点数）记录时间（以 0.1 秒为单位）。由于 0.1 在二进制中是无限循环小数（0.0001100110011...），截断误差在连续运行 100 小时后累积到约 0.34 秒，导致目标位置预测偏差约 600 米，超出了系统的跟踪范围。

这个案例深刻说明了浮点数精度问题在安全关键系统中的严重后果。在长时间运行的系统中，即使微小的舍入误差也可能累积为不可接受的偏差。解决方案包括使用更高精度的数据类型、定期重新校准时间基准，或使用专门的时间表示方法。

4.2 案例二：Intel Pentium FDIV 漏洞

1994 年，Intel Pentium 处理器被发现存在浮点除法漏洞（FDIV bug）。原因是处理器内部用于加速除法的 SRT 除法查找表（PDQROM）中有 5 个条目在制造过程中缺失，导致某些特定的浮点除法运算产生错误结果。虽然错误概率极低（约十亿分之一），但对于科学计算用户来说不可接受。

Intel 最初试图淡化问题，但在公众和学术界的压力下最终实施了全面召回，代价约 4.75 亿美元。这一事件深刻影响了处理器验证方法论：现代处理器在流片前需要进行极其严格的浮点运算验证，包括形式化验证和大规模随机测试。IEEE 754 标准的严格遵循也成为处理器设计的基本要求。

五、常见误区与注意事项

5.1 误区一：浮点数运算是精确的

错误描述：认为计算机的浮点数运算结果与数学上的精确结果一致。

正确理解：浮点数运算本质上是近似运算。除了 2 的幂次和某些特殊值外，大多数实数无法被浮点数精确表示。每次浮点运算都可能引入舍入误差。在编写数值计算程序时，必须考虑精度问题：使用 epsilon 比较浮点数相等性（|a - b| < epsilon），避免灾难性抵消，使用高精度累加算法等。

5.2 误区二：除法总是比乘法慢很多

错误描述：认为除法运算的延迟远大于乘法，应该尽可能用乘法替代除法。

正确理解：虽然除法确实比乘法慢（整数除法延迟通常是乘法的 3-4 倍），但在某些情况下可以用乘法替代。例如，除以常数可以用乘以该常数的倒数来替代（编译器通常会自动进行这种优化）。但对于变量除法，这种替代不可行，因为每次都需要计算倒数。现代处理器的除法单元经过高度优化，实际性能差距在缩小。

5.3 误区三：溢出是可以忽略的小问题

错误描述：认为整数溢出只是极端情况，在正常程序中不会发生。

正确理解：整数溢出是常见的安全漏洞来源。有符号整数溢出在 C/C++ 中是未定义行为（undefined behavior），编译器可以做出任意假设。无符号整数溢出虽然是定义良好的（结果对 2^N 取模），但可能导致逻辑错误。著名的案例包括 Heartbleed 漏洞中的长度溢出检查失败。程序员必须主动检查可能的溢出场景。

5.4 误区四：非规格化数没有实际用途

错误描述：认为非规格化数只是为了完善标准而设计的，实际应用中不会遇到。

正确理解：非规格化数实现了"渐进下溢"（gradual underflow），使得接近零的数值计算仍然保持一定的精度。如果没有非规格化数，所有小于最小规格化数的值都会直接变为零（突然下溢），导致严重的精度损失。在某些科学计算和信号处理应用中，非规格化数的处理可能显著影响性能（因为处理非规格化数的硬件路径通常更慢）。

六、本章小结

本章深入探讨了计算机算术运算的硬件实现。整数加法从半加器/全加器出发，通过行波进位和超前进位两种策略实现不同速度-面积权衡。乘法通过移位-加法、Booth 编码和 Wallace 树等技术逐步优化。除法是最复杂的基本运算，恢复余数和不恢复余数算法各有特点。IEEE 754 浮点数标准为不同平台的数值计算提供了统一规范，但有限的精度带来了精度损失、溢出和下溢等问题。Guard/Round/Sticky 位在浮点运算的精确舍入中扮演关键角色。理解这些底层机制对于编写正确的数值计算程序、进行处理器设计和安全分析都至关重要。

七、思考题与练习

设计一个 4 位超前进位加法器，写出所有进位信号 C1、C2、C3、C4 的逻辑表达式。分析其门级延迟与 4 位行波进位加法器的差异。

使用 Booth 编码计算 6 * (-3) 的过程。将乘数 -3 表示为 4 位补码，列出每一步的部分积和累加结果。

将十进制数 -37.625 转换为 IEEE 754 单精度浮点数格式（写出完整的 32 位二进制表示）。然后将结果转换回十进制验证。

解释为什么 1/3 在二进制浮点数中无法精确表示。计算单精度浮点数表示 1/3 时的相对误差。

设计一个实验，演示"大数吃小数"现象。在单精度浮点数下，从 1.0 开始反复加 2^-20，加多少次后结果不再变化？解释原因。

比较 Kogge-Stone 和 Brent-Kung 前缀加法器在延迟、面积和功耗方面的差异。在什么场景下应选择哪种方案？

分析以下代码的数值精度问题，并提出改进方案：float sum = 0; for (int i = 0; i < 1000000; i++) sum += 0.001f;

讨论为什么 IEEE 754 标准选择"就近舍入到偶数"作为默认舍入模式，而不是"向零舍入"或"向上舍入"。这种选择有什么统计优势？

第3章 计算机的算术运算（硬件计算） Arithmetic for Computers