玻尔百科算术是所有计算的基础，然而，一台由简单开关组成的机器如何执行这些操作，本身就是一项工程奇迹。本文将揭开数字加法的神秘面纱，探讨将抽象数学转化为具体逻辑电路的核心挑战。我们将从二进制加法的基础原理开始，探索如何构建简单的半加器和全加器。然后，我们将研究更高级的架构，如行波进位加法器、超前进位加法器和保留进位加法器，理解速度与效率之间的关键权衡。最后，我们将拓宽视野，看看这些基本电路如何被巧妙地应用于执行减法、比较，甚至与人类可读的数字系统进行通信。本次探索始于使数字算术成为可能的基本原理和机制。
在每一台计算机的核心，从最简单的计算器到最强大的超级计算机，都存在着一个基本操作：加法。但是，一台由开关集合构成的机器，实际上是如何执行像算术这样看似抽象的任务的呢？答案是一段通往计算逻辑的美妙旅程，一个从最基本的概念构建复杂性的故事。让我们开始这段旅程，从零开始构建一个加法器。
首先，让我们考虑最简单的加法：两个单个二进制数字（即比特）相加。我们称它们为 和 。可能的结果有哪些？
这个简单的任务由我们称为半加器的电路执行。它接收两个输入 和 ，并产生两个输出：一个和位 和一个进位输出位 。其逻辑非常直接。仅当输入不同时，和位才为 ，这正是异或（XOR）运算的定义。仅当两个输入都为 时，进位输出位才为 ，这正是与（AND）运算。
这是一个不错的开始，但这还不够。当我们手算多位数加法时，我们先将第一列的数字相加，写下和，然后向下一列进位。关键在于，对于后续的每一列，我们相加的不是两个数字，而是三个：数字本身的两位，加上前一列的进位。
半加器无法完成此任务，因为它只有两个输入。它无法接收来自其右侧列的进位输入（carry-in）。我们需要一个功能更强的模块，一个能处理三个输入的模块。这就引出了数字算术的主力：全加器。
全加器接收三个输入——、 和一个进位输入 ——并产生同样的两个输出：一个和 和一个进位输出 。为了真正理解全加器的作用，我们可以暂时抛开逻辑门，将其看作一个简单的计数机。输入值的总和是算术和 。这个和可以是0、1、2或3。我们如何用二进制表示这些值？
注意一个优美的模式正在显现。两位输出 的值就是 。这给了我们全加器的基本算术恒等式：
这个方程正是全加器之所以为全加器的定义。任何电路，若在任何输入下不满足此恒等式，根据定义，就是一个损坏的加法器。满足此恒等式的逻辑表达式为：
和位就是所有三个输入的异或——它告诉你‘1’的总数是奇数还是偶数。进位输出代表了“多数票”：如果至少有两个输入为1，它就为1。有了这个强大的构建模块，我们现在可以对任意大小的数进行相加了。
我们如何将两个32位的数相加？最直观的方法是模仿我们在纸上的做法，将我们的全加器串联起来。我们对第一位使用一个半加器（因为没有初始进位输入），然后对剩下的31位各使用一个全加器。第0位的进位输出成为第1位的进位输入，第1位的进位输出成为第2位的进位输入，以此类推。
这个优雅的链式结构被称为行波进位加法器（RCA）。它的简洁性就是它的美。然而，这种简洁性背后隐藏着一个深刻的缺陷：它很慢。
想象一排多米诺骨牌。最终的和位 在知道其进位输入 之前无法计算。但 依赖于第30级的结果，而第30级又依赖于第29级，依此类推，一直回溯到最开始。在最坏的情况下——例如，将1与一个全为1的数相加时——在第一位产生的进位必须“行波式”地穿过整个32位链。每个全加器只有在其前一个完成后才能完成自己的计算。这种顺序依赖性产生了一条延迟随比特数线性增长的关键路径。
对于一个8位加法器，最终的和位 可能在输入施加后经过许多门延迟才能准备好，因为它必须等待进位信号蜿蜒穿过前面所有的七级。最终的进位输出 需要的时间甚至更长。对于一个64位加法器，这种延迟可能变得无法忍受，从而限制了整个处理器的时钟速度。
这说明了工程学中的一个重要权衡。行波进位加法器小而简单（它的面积小），但速度慢（它的延迟高）。在另一个极端，可以设计一个位串行加法器，它仅使用一个全加器和一个存储元件，一次一位地将任意长度的两个数相加。这种设计非常紧凑，但对于一个N位的加法需要N个时钟周期，这在另一种意义上非常慢（吞吐率低）。因此，挑战在于找到一种既快速又高效的方法。
为了摆脱行波式传递的缓慢步伐，我们需要天才的火花。与其等待进位到达，不如我们能够预测它？如果每一级都能查看自己的输入 和 ，并在不等待其进位输入的情况下确定其进位输出的命运，会怎么样？这就是超前进位加法器（CLA）背后的革命性思想。
其洞见在于分解产生进位输出的条件。对于任意给定的一级 ，进位输出（）可以通过两种方式发生：
该级自身可以产生一个进位。如果它的两个输入 和 都为1，就会发生这种情况。此时，无论进位输入是什么，它都会产生一个进位。我们称这个信号为 。
该级可以将前一级的进位传递下去。如果该级接收到一个进位输入（）并且处于允许其通过的状态，就会发生这种情况。当其输入 或 中恰好有一个为1时，就会出现这种“传递”状态。此时，它将传播输入的进位。我们称这个信号为 。
现在，我们可以用一个简单而强大的方程来表示任何一级的进位输出：
这表示，如果第 级产生一个进位，或者它传播一个输入的进位，那么第 级的进位输出就为1。虽然这看起来仍然是递归的，但其魔力在于我们展开它时会发生什么。让我们看看前几个进位，假设初始进位输入为 ：
仔细看 的表达式。它只依赖于第0级和第1级的P和G信号，以及初始进位 。它不再依赖于 了！我们已经“向前看了”。我们可以对每个进位都这样做。所有的P和G信号可以同时为所有32位计算出来，只需一个门延迟，因为它们只依赖于主输入 和 。然后，一个称为超前逻辑的专门高速电路可以从这些P和G信号并行计算出所有32个进位。长长的多米诺骨牌链被一个系统所取代，其中每一级的进位都是直接从一个全局信息池中计算出来的。
一旦这个快速进位网络传递了所有的 信号，最终的和位就可以在整个加法器上即时并并行地计算出来，使用的就是我们已经知道的简单关系：。行波传递的束缚被打破了。我们获得了速度。（值得注意的是，自然是巧妙的，存在一些略有不同但等效的方式来定义这些信号，例如使用 ，这也会得到同样辉煌的结果）。
CLA是快速相加两个数的绝佳解决方案。但是，如果要同时相加三个或更多的数呢？这在乘法器中是常见的任务。我们可以使用一系列CLA，但还有一种更激进、更优雅的方法。这个想法是改变问题。与其在每一步都问“最终的和是多少？”，我们不如简单地问“我如何减少需要相加的东西的数量？”
这就是保留进位加法器（CSA）的原理。它的策略是一种高超的拖延术：尽可能地推迟处理进位。
想象一下将三个数 、 和 相加。CSA使用一组独立的全加器，每个位列一个。对于每一列 ，全加器接收三个位 ，并产生一个和位 和一个进位输出位 。这里的关键技巧是：第 级的进位输出不连接到第 级的输入。相反，所有的和位（）被收集到一个我们称之为“和向量”的新数中，而所有的进位位（）则被收集到一个独立的“进位向量”中。
在单个全加器的延迟内，完全没有任何行波传播，我们就把相加三个数的问题简化成了相加两个数（和向量和（移位的）进位向量）的问题。进位被“保存”在它们自己的向量中，而不是被传播出去。
这项技术非常强大。如果你需要相加，比如说，八个数，你可以使用一个CSA树（通常称为华莱士树）将这八个数减少到六个，然后到四个，最后只剩下两个。整个简化过程在极小的、对数级的步骤中完成，每一步只花费单个全加器的延迟。
只有在最后，当我们只剩下最后两个向量时，我们才需要解决进位问题并计算最终答案。而对于这最后一步，我们可以使用我们快速的超前进位加法器。这种用于简化的CSA和用于最终求和的CLA的组合是现代处理器中高速乘法器的支柱。作为一个美妙的副作用，通过避免长长的、行波式的信号链，这种保留进位的方法还可以显著降低电路的功耗。这是一种不仅更快，而且更智能、更高效的设计。
从简单的半加器到保留进位和超前逻辑的复杂交织，加法器的故事本身就是计算机工程的一个缩影：在层层优美简洁而强大的思想之上，对速度和效率的不懈追求。
理解了加法器的工作基本原理——从进位位的耐心行波传递到超前生成器的远见卓识——我们现在可以提出一个真正令人兴奋的问题：我们能用它们做什么？有人可能会天真地认为加法器只用于，嗯，加法。但这就像说小提琴的弦只能发出一个音符一样。加法器，这个计算的基石，其真正的美在于其惊人的多功能性。只需一点巧思，这个简单的电路就能变成减法器、比较器、连接不同数字系统的桥梁，以及高性能计算的核心引擎。它是数字设计的缩影，其中深刻的原理被用来创造优雅而强大的解决方案。
让我们从一个优美的逻辑炼金术开始。计算机是如何进行减法的？它是否有一套完全独立的电路专门用于减去数字？答案，奇妙的是，不。它使用一个加法器。其魔力在于一种称为二进制补码的数字表示法。为了计算 ，机器巧妙地计算 。 的负数是通过首先将其所有位取反（“反码”），然后加一得到的。
那么这个“+1”从何而来呢？在一个效率的杰作中，我们只需将加法器的初始进位输入 设置为1。并行加法器接收数字 、 的反码位和一个值为1的“高电平”进位输入。然后它执行其通常的加法，而得到的结果恰好是差值 。减法，这个我们学习时作为一个独立操作的概念，被揭示为不过是加法的一种伪装形式。这种统一证明了二进制算术的优雅。
但魔法并未就此结束。当加法器计算差值时，它免费地给了我们另一条信息。来自最高有效位的最终进位输出位，一个否则可能看起来无关紧要的溢出位，变成了一个强大的信使。如果我们正在减去两个无符号数 ，这个最终的进位输出位 告诉我们它们相对大小的信息。如果 为1，这意味着不需要从一个想象中的更高位“借位”，这直接意味着 。如果 为0，则表示 大于 ，并且需要借位。因此，通过一次操作，我们的加法器电路不仅执行了减法，还充当了数值比较器。这是工程师和物理学家梦寐以求的那种深刻的效率——从一个统一的过程中提取最大量的信息。
虽然计算机以纯粹、抽象的二进制语言思考，但它们常常必须以我们人类用于从金融交易到读取数字时钟等一切事务的十进制系统来传达结果。这需要能够“说”十进制的硬件。解决方案是二-十进制（BCD）加法器。在BCD中，每个十进制数字（0-9）都由其自己的4位二进制代码表示。
当我们相加两个BCD数字时，比如5（0101）和8（1000），一个标准的4位二进制加法器会得出13（1101）。这是一个完全有效的4位数字，但它不是一个有效的BCD数字——10到15的代码是未使用的。结果应该是一个BCD的‘3’（0011）和一个向下一个十进制位的进位输出。我们该如何修正这个问题？电路会执行一次校正。它首先检测二进制和是否无效（大于9）。如果是，电路会在结果上加上一个校正因子6（0110）。为什么要加6？因为有六个未使用的4位模式（1010到1111），我们必须“跳过”它们以绕回到有效的BCD范围内。加上6会自动产生正确的BCD数字并生成必要的十进制进位。这个BCD加法器是一件优美的工程作品，一个站在机器世界和我们自己世界接口处的翻译官。
在每个处理器的核心，加法器都在与时间赛跑。整个计算机的速度往往归结为它能多快地执行一次加法。这种对速度的追求导致了一系列引人入胜的设计选择和巧妙的优化。
正如我们所见，简单的行波进位加法器（RCA）结构紧凑，但其速度受到进位信号从一端传播到另一端的“多米诺效应”的限制。对于快速处理器来说，这通常太慢了。另一种选择是超前进位加法器（CLA），它使用更复杂的一块逻辑来并行计算所有进位。它“向前看”而不是等待。这使其速度显著加快，但代价是体积更大、功耗更高。这两种设计之间的选择是一个经典的工程权衡。选择更快的CLA可以让整个微处理器以更高的时钟频率运行，每秒执行更多指令。每一部智能手机、笔记本电脑和超级计算机都包含了这一基本决策的结果，平衡了对速度的需求与物理尺寸和功耗的限制。
然而，我们并非总是需要一个强大的通用加法器。有时，我们有一个非常具体的任务，比如简单地给一个数加1（这个操作称为递增）。如果我们分析一个强大的CLA在这种特殊情况下的逻辑，我们会发现复杂的方程会坍缩成非常简单的东西。例如，在一个4位递增器中，确定整个模块是否会产生进位的逻辑简化为仅仅检查所有输入位是否都为1（即输入是否为 ）。对一般原理的深刻理解使我们能够为特定任务构建一个高度优化、更小、更快的电路。这种专业化原则在工程中无处不在，从设计赛车引擎而不是通用引擎，到为特定算法编写优化代码。
另一个微妙而绝妙的专业化例子发生在相加不同位宽的数字时，比如一个8位数和一个4位数。较小的数字必须被“符号扩展”以匹配较大数字的位宽。与其为此设置一个单独的电路，符号位的影响可以直接集成到加法器逻辑中。如果4位数是负数，其符号位为1。这在数学上等同于在高位加上一个全为1的块。例如，加上-1（在4位二进制补码中是 ）与加上无符号值15是相同的。这个固定的偏移量可以直接构建到加法器的上部，通过将符号扩展和加法融合成一个优化的步骤来节省时间和硬件。
在计算机图形学、科学模拟和数字信号处理等领域，挑战通常不是单次加法，而是将一长串数字相加。在这里，一种不同类型的加法器架构大放异彩：保留进位加法器（CSA）。CSA接收三个输入数，但不是产生一个单一的和，而是输出两个数：一个部分和向量和一个进位向量。注意，它没有解决进位问题；它只是把它们“保存”起来以备后用。我们可以将这些CSA排列成树状结构，将一大组数字（比如四个或八个）简化为仅仅两个向量。
这种方法的美妙之处在于，通过CSA树的延迟不依赖于数字的位宽，这与行波进位加法器不同。我们有效地将缓慢的进位传播推迟到了最后一步。在最后，我们使用一个单一的、常规的（最好是非常快的，比如CLA）加法器来将最终的和向量与进位向量相加，得到真正的结果。这是一种系统级策略：它重构了整个问题，将加法中缓慢的部分隔离出来，并只在最后执行一次。
到目前为止我们讨论的所有设计通常都是同步的，随着全局时钟的节拍同步进行。时钟周期必须足够长，以适应绝对最坏情况下的延迟，即使这种情况很少发生。但是，如果我们能构建一个电路，在完成时简单地发出信号呢？这就是异步设计背后的哲学。例如，一个异步行波进位加法器，如果进位只需要传播很短的距离，它可能会非常快地完成计算。它不必等待最坏情况的发生。通过将输入建模为随机的，我们可以计算平均情况下的延迟。在某些条件下——具体来说，当“我完成了”信号的硬件开销足够低时——异步加法器的平均性能可以超过其同步对应物的保证最坏情况性能。这代表了一条不同的性能提升路径，一条基于概率和平均情况行为而非最坏情况保证的路径。
最后，一个真正有用的算术单元不仅要能计算，还必须能识别其结果何时是无意义的。在二进制补码算术中，将两个大的正数相加可能会产生一个“环绕”并呈现为负数的结果。这被称为溢出，是一个关键的错误条件。ALU（算术逻辑单元）必须能够检测到它。
在这里，我们再次找到了一个惊人简单而优雅的解决方案。最高有效位（符号位）的逻辑涉及到一个进位输入 和一个进位输出 。事实证明，当且仅当这两个进位位不同时，才会发生溢出。就是这样。一个单一的异或门，，就足以监控整个操作的完整性。另一个同样有效的方法是检查输入和输出的符号：只有当你将两个相同符号的数相加，得到一个符号相反的结果时，才会发生溢出。这两种方法都是紧凑而巧妙的逻辑片段，赋予处理器一种自我意识，使其能够标记错误并确保计算的可靠性。
从相加两个比特的简单行为开始，我们穿越了计算机体系结构、数论和高性能计算的领域。加法器不仅仅是一个组件；它是一块画布，上面描绘了效率、权衡和逻辑优雅的基本原则。对它的研究揭示了，在我们最复杂的数字机器的核心，存在着被巧妙应用的简单思想。