第七章 二进制加法器 — 算术运算

导读

在前面的章节中，我们学会了用逻辑门处理逻辑信息——判断真假、做选择、比较大小。但计算机不仅要处理逻辑，还要做数学运算。加减乘除，这些我们在小学就学会的基本运算，计算机是如何完成的呢？

答案可能比你想象的要简单。计算机的算术运算本质上也是逻辑运算——通过巧妙地组合逻辑门，可以构建出执行加法、减法等算术操作的电路。其中，加法器（Adder）是最基本、最重要的算术电路，因为所有的算术运算最终都可以归结为加法操作。

本章将从零开始，一步步构建二进制加法器。我们将从最简单的半加器开始，然后构建全加器，再将多个全加器级联成多位加法器。我们将学习如何用加法器实现减法，了解进位传播的问题和解决方案，最后探索乘法器和除法器的基本原理。通过本章的学习，你将亲眼看到抽象的二进制数如何在物理电路中完成算术运算。

核心概念详解

7.1 二进制加法规则

在构建加法器电路之前，我们先回顾一下二进制加法的规则。二进制加法与十进制加法类似，只是进位规则不同：逢二进一（而不是逢十进一）。

一位二进制加法规则：

0 + 0 = 0    （和=0，进位=0）
  0 + 1 = 1    （和=1，进位=0）
  1 + 0 = 1    （和=1，进位=0）
  1 + 1 = 10   （和=0，进位=1）

考虑来自低位的进位时：

0 + 0 + 0 = 0    （和=0，进位=0）
  0 + 0 + 1 = 1    （和=1，进位=0）
  0 + 1 + 0 = 1    （和=1，进位=0）
  0 + 1 + 1 = 10   （和=0，进位=1）
  1 + 0 + 0 = 1    （和=1，进位=0）
  1 + 0 + 1 = 10   （和=0，进位=1）
  1 + 1 + 0 = 10   （和=0，进位=1）
  1 + 1 + 1 = 11   （和=1，进位=1）

从这些规则中，我们可以提取出两个关键观察：

和（Sum）：当三个输入中有奇数个1时，和为1；否则为0。这恰好是异或（XOR）运算。

Sum = A ⊕ B ⊕ Cin

进位（Carry）：当三个输入中至少有两个为1时，产生进位。

Cout = A·B + A·Cin + B·Cin

7.2 半加器（Half Adder）

半加器是最简单的加法电路，它只能处理两个一位二进制数的相加，不考虑来自低位的进位。

输入：A、B（两个一位二进制数）

输出：S（和）、C（进位）

真值表：

逻辑表达式：

• S = A ⊕ B（异或）
• C = A · B（与）

电路实现：只需要一个XOR门和一个AND门。

半加器之所以叫"半"加器，是因为它只能处理两个输入的相加，不能处理来自低位的进位输入。在实际的多位加法中，每一位都需要考虑来自低位的进位，因此半加器只能用于最低位（最低位没有来自更低位的进位）。

7.3 全加器（Full Adder）

全加器可以处理三个一位二进制数的相加：两个加数和一个来自低位的进位。

输入：A、B（两个加数）、Cin（来自低位的进位）

输出：S（和）、Cout（向高位的进位）

真值表：

逻辑表达式：

• S = A ⊕ B ⊕ Cin
• Cout = A·B + A·Cin + B·Cin = A·B + Cin·(A ⊕ B)

电路实现：可以用两个半加器和一个OR门来构建全加器：

第一个半加器计算 A ⊕ B 和 A·B

第二个半加器计算 (A ⊕ B) ⊕ Cin 和 (A ⊕ B)·Cin

OR门将两个进位项合并：Cout = A·B + (A ⊕ B)·Cin

7.4 行波进位加法器（Ripple Carry Adder）

将多个全加器级联，就构成了行波进位加法器（也称为串行进位加法器）。每个全加器处理一位的相加，并将进位传递给下一级。

4位行波进位加法器：

Cin
         |
  ┌──────┴──────┐
  │  全加器 0    │──→ C0
  │ A₀ B₀       │
  └─────────────┘
         C0
          |
  ┌──────┴──────┐
  │  全加器 1    │──→ C1
  │ A₁ B₁       │
  └─────────────┘
         C1
          |
  ┌──────┴──────┐
  │  全加器 2    │──→ C2
  │ A₂ B₂       │
  └─────────────┘
         C2
          |
  ┌──────┴──────┐
  │  全加器 3    │──→ C3（最终进位）
  │ A₃ B₃       │
  └─────────────┘

输入：A₃A₂A₁A₀、B₃B₂B₁B₀（两个4位二进制数）、Cin（初始进位，通常为0）

输出：S₃S₂S₁S₀（4位和）、Cout（最终进位）

行波进位加法器的优点是结构简单、易于扩展。但它的致命缺点是速度慢。

速度分析：假设每个全加器的传播延迟为T_FA，则n位行波进位加法器的总延迟为n × T_FA。这是因为进位必须从最低位逐级传播到最高位。对于4位加法器，最坏情况下（如1111 + 0001），进位需要经过4个全加器，延迟为4 × T_FA。对于32位加法器，延迟为32 × T_FA；对于64位加法器，延迟为64 × T_FA。

这种线性增长的延迟在高速CPU中是不可接受的。为了解决这个问题，工程师们设计了更快的加法器结构。

7.5 超前进位加法器（Carry Lookahead Adder）

超前进位加法器（CLA）通过并行计算进位来消除行波进位的延迟。

核心思想是：不等待进位从低位逐级传播，而是直接根据输入数据计算出每一位的进位。

定义两个中间信号：

• 生成信号（Generate）：Gᵢ = Aᵢ · Bᵢ（该位本身会产生进位）
• 传播信号（Propagate）：Pᵢ = Aᵢ ⊕ Bᵢ（该位会传递来自低位的进位）

则每一位的进位可以表示为：

• C₀ = G₀ + P₀ · Cin
• C₁ = G₁ + P₁ · G₀ + P₁ · P₀ · Cin
• C₂ = G₂ + P₂ · G₁ + P₂ · P₁ · G₀ + P₂ · P₁ · P₀ · Cin
• C₃ = G₃ + P₃ · G₂ + P₃ · P₂ · G₁ + P₃ · P₂ · P₁ · G₀ + P₃ · P₂ · P₁ · P₀ · Cin

这些表达式可以直接用逻辑门实现，不需要等待前级的进位。因此，超前进位加法器的延迟不再随位数线性增长，而是取决于逻辑门的级数。

代价：超前进位加法器的电路复杂度随位数呈指数增长（进位表达式越来越长）。因此，实际的CLA通常采用分组策略：将加法器分成若干小组（如4位一组），组内使用CLA，组间使用行波进位，形成分组超前进位加法器。

7.6 用加法器实现减法

计算机中通常不单独设计减法器，而是利用加法器来实现减法。这得益于补码的巧妙设计：A - B = A + (-B)，而-B的补码等于B的补码取反加1。

4位减法器电路：

1（Sub控制信号）
         |
  ┌──────┴──────┐
  │  XOR门 × 4  │
  │ B₀→B₀'      │
  │ B₁→B₁'      │
  │ B₂→B₂'      │
  │ B₃→B₃'      │
  └─────────────┘
         │
  ┌──────┴──────┐
  │  4位加法器   │
  │ A + B' + 1  │
  └─────────────┘

当Sub=0时（加法模式）：

• XOR门不改变B的值（B ⊕ 0 = B）
• Cin = 0
• 结果 = A + B

当Sub=1时（减法模式）：

• XOR门将B取反（B ⊕ 1 = B'）
• Cin = 1
• 结果 = A + B' + 1 = A + (-B) = A - B

这种设计的优雅之处在于：加法和减法共用同一套硬件（加法器+XOR门），只需要一个控制信号（Sub）来切换模式。

7.7 算术逻辑单元（ALU）

算术逻辑单元（ALU）是CPU中执行算术和逻辑运算的核心部件。一个简单的ALU可以执行加法、减法、AND、OR等多种操作。

4位ALU的基本结构：

A₃A₂A₁A₀    B₃B₂B₁B₀
             |           |
        ┌────┴───────────┴────┐
        │    4位加法器         │
        │  （B经过操作选择）    │
        └────────┬────────────┘
                 |
        ┌────┴────────────┐
        │  操作选择逻辑    │
        │  （MUX）         │
        └────────┬────────┘
                 |
           S₃S₂S₁S₀

操作选择信号（如2位选择码S₁S₀）决定ALU执行哪种操作：

• 00：AND → 输出 A AND B
• 01：OR → 输出 A OR B
• 10：ADD → 输出 A + B
• 11：SUB → 输出 A - B

实际的ALU远比这复杂，还可能包括移位、比较、取反等操作。

7.8 乘法器

二进制乘法比加法复杂得多。让我们先回顾二进制乘法的规则：

1011  (11)
    × 1101  (13)
    ------
      1011  (11 × 1)
     0000   (11 × 0，左移1位)
    1011    (11 × 1，左移2位)
   1011     (11 × 1，左移3位)
   --------
  10001111  (143)

二进制乘法的每一位要么是被乘数本身（当乘数位为1时），要么是0（当乘数位为0时）。因此，二进制乘法可以分解为一系列的移位和加法操作。

最简单的乘法器实现是使用"移位-加法"算法：

从乘数的最低位开始

如果当前位为1，将被乘数加到部分积中

将被乘数左移一位

将乘数右移一位

重复步骤2-4，直到乘数为0

这种方法的硬件实现相对简单，但速度较慢（需要n个时钟周期来完成n位乘法）。

阵列乘法器（Array Multiplier）是一种更快的并行乘法器。它使用一个二维阵列的加法器来同时计算所有的部分积并相加。对于n位×n位的乘法，阵列乘法器需要大约n²个全加器，但只需要O(n)的门延迟。

现代CPU中的乘法器通常使用更复杂的算法，如Booth编码、Wallace树等，以进一步减少延迟和面积。

7.9 除法器

除法是最复杂的算术运算。二进制除法的过程与十进制除法类似，通过反复的比较、减法和移位来完成。

恢复余数除法的基本步骤：

将被除数的高n位与除数比较

如果被除数 ≥ 除数，商1，做减法

如果被除数 < 除数，商0

将被除数左移一位（或除数右移一位）

重复步骤1-4

非恢复余数除法是恢复余数除法的改进版本，它避免了"恢复余数"的步骤，通过加减交替来简化操作。

SRT除法是一种更高效的除法算法，使用冗余数字系统，允许商位取{-1, 0, 1}三个值，从而减少迭代次数。现代CPU中的除法器通常基于SRT算法。

与乘法器不同，除法器通常采用迭代方式实现，因为并行除法器的硬件代价太高。一个n位的除法通常需要n个时钟周期。

7.10 溢出检测

在有限位数的二进制运算中，结果可能超出表示范围，这种情况称为溢出（Overflow）。

无符号数加法溢出：当最高位产生进位时发生溢出。例如，4位无符号数的范围是0-15，12 + 5 = 17 > 15，发生溢出。

有符号数（补码）加法溢出：当两个正数相加得到负数，或两个负数相加得到正数时发生溢出。

溢出检测电路：

• 无符号数：V = Cout（最高位的进位）
• 有符号数：V = Cn ⊕ Cn-1（最高位进位与次高位进位的异或）

溢出检测是CPU中异常处理的重要组成部分。当溢出发生时，CPU会设置状态寄存器中的溢出标志位，操作系统可以根据这个标志位采取相应的处理措施。

重要知识点

知识点一：半加器和全加器

半加器处理两个一位数的相加，全加器处理三个一位数（含进位）的相加。全加器可以用两个半加器和一个OR门构建。

知识点二：行波进位加法器简单但慢

行波进位加法器将全加器级联，结构简单但速度慢，因为进位必须逐级传播。

知识点三：超前进位加法器通过并行计算进位提高速度

CLA直接计算每一位的进位，消除了进位传播延迟，但电路复杂度较高。

知识点四：减法可以用加法实现

利用补码的性质，A - B = A + (-B)，其中-B = B取反加1。这使得加法和减法可以共用硬件。

知识点五：ALU是CPU的运算核心

ALU通过操作选择信号，可以在同一套硬件上执行多种算术和逻辑运算。

常见误区

误区一："计算机有专门的减法器"

大多数计算机不设计专门的减法器。减法通过补码转换为加法，使用同一套加法器硬件完成。这体现了补码设计的精妙之处。

误区二："加法器的速度不重要，反正很快"

在CPU中，加法器位于关键路径上，其速度直接决定了CPU的时钟频率。一个慢的加法器会拖慢整个CPU的性能。这就是为什么工程师们投入大量精力设计高速加法器。

误区三："乘法就是反复加法"

虽然乘法在数学上可以理解为反复加法，但在硬件实现中，这种方式的效率极低。实际的乘法器使用移位-加法或并行阵列的方式，大大减少了操作次数。

误区四："溢出和进位是一回事"

进位（Carry）是无符号数运算中的概念，表示结果超出了无符号数的表示范围。溢出（Overflow）是有符号数运算中的概念，表示结果超出了有符号数的表示范围。两者的检测方法不同。

实践应用

应用一：设计一个4位行波进位加法器

使用全加器模块，设计一个4位行波进位加法器：

画出完整的电路图

计算最坏情况下的传播延迟

验证 1011 + 0110 的计算过程

应用二：用加法器实现减法

设计一个4位加减法切换电路：

画出电路图（包括XOR门和加法器）

验证 7 - 3 = 4 的计算过程

验证 3 - 7 的结果（考虑补码表示）

应用三：分析溢出

对于4位有符号数（补码，范围-8到+7），判断以下运算是否溢出：

5 + 3

(-4) + (-5)

6 + (-2)

(-3) + (-4)

应用四：设计简单的ALU

设计一个2位ALU，支持以下操作：

• 00：AND
• 01：OR
• 10：ADD
• 11：NOT A

本章小结

本章系统地介绍了二进制算术运算电路的设计：

半加器和全加器：全加器是构建多位加法器的基本单元，可以处理两个加数和一个进位输入。

行波进位加法器：结构简单但速度慢，进位逐级传播。

超前进位加法器：通过并行计算进位提高速度，是高速CPU中的常用方案。

减法实现：利用补码，减法可以转换为加法，共用硬件。

ALU：通过操作选择，在同一套硬件上执行多种运算。

乘法和除法：乘法通过移位-加法实现，除法通过比较-减法-移位实现。

溢出检测：区分无符号数的进位和有符号数的溢出，采用不同的检测方法。

从加法器到ALU，我们已经构建了计算机的"算术大脑"。但一个完整的计算机不仅需要计算能力，还需要记忆能力——能够存储数据和程序。在下一章中，我们将探索计算设备从算盘到芯片的演进历程，理解存储和计算是如何结合在一起的。