玻尔百科在对计算速度不懈的追求中，每一纳秒都至关重要。从您口袋里的手机到模拟我们气候的超级计算机，现代处理器的性能取决于它们以惊人速度执行算术运算的能力。然而，在这种复杂性的核心，潜藏着一个我们在小学就学过的基本运算：加法。在这个简单的过程中，潜伏着一个隐藏的瓶颈——进位的涟漪式传播——几十年来一直挑战着工程师们。传统加法中进位的顺序依赖性产生了一条延迟链，从根本上限制了我们的计算速度。
本文探讨了进位保留算法（Carry-Save Arithmetic, CSA），这是一种巧妙而强大的技术，它聪明地绕过了这个瓶颈。CSA 并不与进位作斗争，而是采纳了一种智能的“拖延”原则：将困难的进位传播工作推迟到最后才做。通过这样做，它释放了大规模的并行性，并极大地加快了计算速度，尤其是在需要同时对许多数字进行相加时。
我们将首先探讨进位保留算法的基础“原理与机制”，剖析它如何利用简单的逻辑门，用许多独立的快速加法来换取一次缓慢的加法。然后，我们将历览其“应用与跨学科联系”，探索这一思想如何彻底改变从硬件乘法器设计、高性能 CPU 架构到抽象理论算法实现的方方面面。
要理解进位保留算法的精妙之处，我们必须首先直面我们都被教导过的加法方法中的根本瓶颈：进位。想象一下用手计算两个大数相加。你从右到左，一列一列地进行。在每一列中，你将数字相加，写下结果数字，如果和大于等于10，你就向下一列“进”一个一。这个过程简单可靠。这也正是一个基本计算机加法器——行波进位加法器的工作方式。
行波进位加法器由一串称为全加器的简单组件构成。每个全加器都是一个微型电路，它知道如何将三个单位比特相加：两个来自待加数的输入比特，以及一个来自其右侧列的进位输入比特。它产生两个输出：一个用于其自身列的单位和比特，以及一个用于其左侧列的进位输出比特。
问题就出在这里。第二列的全加器必须等到接收到第一列的进位输出后才能开始工作。第三列必须等待第二列，第四列等待第三列，依此类推。对于两个 64 位数字的加法，在第一位产生的进位可能需要一路传播，或称“行波”，一直传到第 64 位。这就产生了一条依赖链，一场每一级都被前一级所牵制的等待游戏。对于每秒发生数十亿次运算的高速计算而言，这种行波延迟是不可接受的制约。
进位保留算法提出了一个绝妙的解决方案：如果进位是问题所在，为什么不干脆……把它推迟处理呢？我们不必在每一步都立即解决进位问题，而是可以简单地把它保存起来留待后用。这是一种智能的“拖延”，打破了拖慢一切的依赖链。
让我们看看这在最基本的层面上是如何运作的。想象我们不是在加两个数，而是三个数：、 和 。在任意给定的比特列 中，我们现在有三个比特要求和：、 和 。这个和的结果可以是 ()、 ()、 () 或 ()。一个输出比特已不足以表示这个和。但一个两位二进制数就非常合适！我们可以将和表示为一个两位值 ，其中 是低位（“和”）， 是高位（“进位”）。
例如，如果我们计算 ，两位结果是 。所以我们会输出一个为 的和比特和一个为 的进位比特。如果我们计算 ，结果是 ，得到一个为 的和比特和一个为 的进位比特。规则很简单：和比特 是该列加法忽略任何进位输出的结果，而进位比特 是本应传递给下一列的比特。
执行这项基本任务的电路正是我们所熟悉的全加器。它接收三个比特作为输入，并产生两个比特作为输出。其输出在数学上定义为：
这里， 是异或（XOR）运算，它给出不考虑进位的和比特。进位输出由“多数”函数决定：如果输入比特中至少有两个为 1，则进位为 1。其魔力在于这两个输出完美地保留了原始的和：。
因为这个单一组件接收三个输入并将其计数表示为一个两比特输出，所以它通常被称为 (3,2) 计数器或 (3,2) 压缩器。它将三股比特流压缩成两股，而没有任何信息损失。
现在，让我们来构建我们的机器。要将三个 位数字相加，我们只需并排排列 个这样的全加器，每个比特列一个。关键特性是这些全加器不是串联的。第 列的全加器接收比特 ，其工作完全独立于任何其他列的全加器。它们全部并行操作。
由于我们的 个全加器中的每一个都产生两个输出，整个装置并不产生单一的答案。相反，它产生两个 位向量：
一个部分和向量 (S)：该向量由收集所有和比特构成，。这是如果你仅使用异或（XOR）运算来加这三个数，完全忽略所有进位时会得到的结果。
一个部分进位向量 (C)：该向量由收集所有进位比特构成。然而，从第 列产生的进位 的权重是第 列比特的两倍；它理应属于第 列。因此，进位向量实际上向左移动了一个位置。原始三个数的总和在这种新形式中被完美地保留下来：，其中 表示向左移一位。
我们用两个中间答案换取了单一的、确定的答案。这被称为冗余表示法，因为同一个数值可以由不同的 S 和 C 向量对来表示。这似乎是退了一步，但这正是我们速度的源泉。我们执行了加三个数的困难任务，并将其简化为加两个数的更简单的任务，而且我们只用了一个全加器操作的时间就完成了，无论我们加的是 8 位还是 128 位数字。
单个 CSA 级的延迟是恒定的。它就是信号通过一个全加器所需的时间，这与比特数 无关。这与行波进位加法器形成鲜明对比，后者的延迟与 成正比。
当我们需要相加许多数字时，比如八个——这是数字信号处理或乘法中的常见任务——这种方法的真正威力就显现出来了。一种天真的方法是使用一串七个行波进位加法器。延迟将是巨大的，因为我们必须等待进位行波传播七次。
使用进位保留算法，我们构建一个 CSA 树。
这棵树中的每一级都非常快，延迟只有一个全加器的时间。将八个数减少到两个的总时间仅仅是几个全加器延迟的时间。我们用一个短暂的、对数级的等待替换了一个漫长的、线性的等待。
当然，最终我们需要一个单一的、非冗余的数字作为我们的答案。我们有两个向量，S 和 C。现在，且仅在现在，我们才支付进位传播的代价。我们使用一个常规的加法器，称为进位传播加法器 (CPA)，通过将部分和向量 S 与移位后的部分进位向量 C 相加来计算最终的和。
是的，这最后一步涉及到一次行波（或一个更复杂但更快的超前进位方案），但我们只需要做一次。我们将所有痛苦的进位逻辑整合到了一次单一的、最终的操作中，而在此之前，大部分的求和工作已经在快得惊人的、并行的进位保留世界中完成了。
这种非凡的速度伴随着一个微妙的权衡。虽然 S 和 C 向量完美地编码了最终的和，但这个值并不是“显式”的。如果在某个中间步骤后，你需要问一个简单的问题，比如“这个部分和是正数还是负数？”或者“是否发生了溢出？”，你无法仅仅通过查看 S 和 C 向量来找到答案。
在二进制补码格式中，一个数的符号由其最高有效位给出。但和的真正最高有效位取决于进位一路行波传播到顶端。在你执行最终的进位传播加法之前，真正的最终值仍然隐藏在冗余表示中。对于许多应用，如乘法，我们只关心最终的乘积，这是一个完美的权衡。我们甘愿牺牲中间信息的明晰性，以换取整体吞吐量的巨大提升。进位保留算法是工程妥协的一个美丽典范，一个绝妙的洞见，即通过策略性地延迟一项计算，我们可以使整个过程变得更快。
在理解了进位保留算法的原理——即通过分离和与进位比特来绕过缓慢、顺序的进位传播过程的巧妙技巧——之后，我们现在可以踏上一段旅程，看看这个简单的想法将我们带向何方。它确实将我们带到了一些非常了不起的地方。如同物理学和工程学中的许多深刻概念一样，它的美不仅在于其内在的优雅，还在于其惊人而深远的影响。我们将看到，这一个思想在计算的各个层面回响，从单个微芯片的设计到最强大处理器的架构，甚至延伸到理论算法的抽象世界。这是科学与工程中统一性的一个绝佳范例。
进位保留方法的核心，本质上是一门“拖延”的艺术。想象一个泥瓦匠团队正在砌一堵长墙。行波进位系统就像一条规则，规定第二个泥瓦匠必须等到第一个泥瓦匠完全砌平自己的砖块并确认没有“遗留”工作后才能铺砖。第三个泥瓦匠等待第二个，如此类推。这个过程很慢，受限于最谨慎工人的速度。而进位保留方法则不同。它告诉每个泥瓦匠以最快的速度同时铺砖。如果一块砖没有完全对齐，他们不会停下来；他们只是在上面放一个小标记——一个“进位”标记——表示一笔稍后要结清的小工作债。在一个迅速的并行步骤中，整层墙壁几乎就完成了。只有在最后，才有一位专家前来结清所有债务，根据标记修复对齐问题。通过推迟困难的、顺序性的部分，整个过程变得显著加快。
进位保留算法最直接、最深刻的应用是构建能够同时对多个数进行加法的硬件，这是无数计算问题的核心任务。如果你需要求和，比如说，八个不同的数，将标准加法器串联起来的天真方法，就如同我们那排等待的泥瓦匠。前两个数相加，然后结果与第三个数相加，依此类推。每一次加法都必须等待前一次完成其全部的进位传播。总时间是一个加法器的延迟乘以七。
然而，一个进位保留加法器（CSA）树的运作方式就像我们第二支泥瓦匠团队。它接收三个数，在一个与位数无关的、恒定时间的步骤内，将它们简化为两个数：一个和向量和一个进位向量。我们可以将这些 CSA 模块排列成一个树形结构，迅速地将我们最初的八个数减少到只剩下两个。对于一个对八个 16 位数求和的系统，这种 CSA 树方法比串行链式常规加法器快五倍以上。这不仅仅是一个小小的优化；这是性能格局的根本性改变。
这一点在硬件乘法器中尤为关键。当你乘以两个数，如 时，你会生成一系列必须相加的“部分积”。对于两个 位数，你最多可以生成 个这样的部分积。将它们相加是一个大规模的多操作数加法问题，整个乘法的速度都由这一步主导。这正是进位保留算法的“杀手级应用”。著名的华莱士树（Wallace Tree）乘法器正是这一思想的直接而优美的体现。它本质上是一个专门为将部分积比特矩阵减少到最后一对和与进位向量而构建的 CSA 树。用于这个规约树所需的全加器数量甚至可以用一种惊人优雅的方式计算出来；它就是你开始时的总比特数减去你结束时的总比特数（在两个最终向量中），因为每个全加器都充当一个 3 到 2 的压缩器，将总比特数减少一。
当然，“拖延”只是推迟了不可避免的事情。最终的和与进位向量最终必须使用一个常规的、进位传播的加法器（CPA）相加。这最后一步可能成为一个瓶颈。工程师们使用像 Kogge-Stone 加法器这样极其快速、复杂的加法器来进行这最后的“清算日”。这导致了一个有趣的权衡：对于少量初始操作数，复杂最终加法器的延迟实际上可能大于 CSA 树本身的延迟。这提醒我们，工程总是一场权衡的游戏，是在不同架构选择之间找到最佳平衡点。
进位保留算法的影响远远超出了专门的乘法器电路。其延迟进位传播的理念渗透到现代处理器的设计中。
考虑一个高性能的算术逻辑单元（ALU），即 CPU 的计算核心。如果它需要计算多个操作数的和，比如 ，它可以按照进位保留的原则进行设计。在流水线处理器中，任务可以被划分到不同阶段。第一阶段可以使用两层 CSA 将四个输入减少为两个向量 。这个阶段非常快，因为它的延迟与操作数宽度（例如 64 位）无关。第二阶段随后可以执行那一次缓慢的进位传播加法以获得最终结果。通过将缓慢的部分隔离在自己的流水线阶段，处理器的整体吞吐量得以维持。
这一思想在乘累加（MAC）单元中达到了顶峰，它是数字信号处理（DSP）的主力。许多 DSP 算法，如有限冲激响应（FIR）滤波器，本质上是一长串“乘积之和”的计算。一个 MAC 单元必须一遍又一遍地计算 。一个天真的实现方式会在每个周期内执行一次完整的乘法和一次完整的加法，其中加法的长进位传播延迟会限制时钟速度。然而，一个进位保留累加器将运行总和 保持为冗余的进位保留形式 。在每个周期中，它使用 CSA 将新的乘积 （也可能以进位保留形式存在）与这对向量相加。每个周期的关键路径仅仅是单个 CSA 的延迟，一个很小的恒定值。那个漫长的、与宽度相关的进位传播完全从循环中被移除，只在最后需要最终结果时执行一次。这使得 MAC 单元能够以极高的速度运行。
这种影响在编程和微体系结构层面是直接可见的。将一个简单的处理器升级以支持使用集成 CSA 的三输入加法，可以将原本需要两个独立微操作（因此需要两个时钟周期）的任务，缩减为在单个周期内执行的原子微操作。对于一个执行此计算数百万次的循环，这种简单的硬件增强直接转化为总执行时间的大幅减少。
此外，这一原则可扩展到高性能和科学计算领域。在处理远超单个机器字长度的多精度算术时，加法是通过一连串带进位加法指令逐字执行的。这产生了严格的数据依赖性，因为每个字的加法都必须等待前一个字的进位。这个依赖链实际上串行化了计算，阻止了强大的超标量处理器利用其并行执行指令的能力（指令级并行，或 ILP）。ILP 被压缩到 1。通过采用进位保留方法，其中逐字操作并行完成以产生和与进位向量，这个依赖链被打破了。处理器现在可以并行发出许多指令，从而显著提高性能。
到目前为止，我们已将进位保留视为一种硬件技巧。但当我们将其视为更根本的东西时，其最深远的含义便浮现出来：数字表示法的改变。向量对 是一个数字的冗余表示法，意味着同一个数值可以由多个不同的 对来表示。正是拥抱这种冗余性，才解锁了并行性。
这一思想在最先进的乱序执行处理器的设计中具有深远的影响。在这些 CPU 中，指令被推测性地执行，其结果被保存在一个微体系结构缓存（重排序缓存）中，直到它们可以按程序顺序提交到官方的体系结构状态。一个前沿的设计可能会在整个流水线中都将乘法的结果保持为其冗余的进位保留形式 。最终的、缓慢的进位传播加法被推迟到最后一刻：提交阶段。这是“拖延”的终极形式。人们可能会担心这会破坏机器精确处理异常的能力，因为“真实”结果及其相关的状态标志（如溢出）直到最后才为人所知。然而，由于所有体系结构更新都在提交时按序发生，系统仍然是完全可靠的。CPU 可以在结果变得可见之前计算最终结果并检查溢出异常，从而确保体系结构状态始终保持一致。这揭示了低级算术表示与处理器正确性的最高层保证之间美丽而微妙的相互作用。
故事并未止于硬件。完全相同的原则在理论算法的抽象世界中再次出现。考虑 Karatsuba 乘法，这是一种著名的分治算法，它以大约 的时间复杂度乘以两个 n 位数，比小学方法更快。该算法涉及递归乘法和一个需要加法和减法的“重组”步骤。如果这些中间加法使用标准的进位传播逻辑执行，它们将在每一层递归中贡献线性时间成本。然而，如果使用冗余的进位保留表示法来实现整个算法的所有中间值，这些代价高昂的传播几乎可以完全消除，取而代之的是快速、并行的 CSA 操作。虽然这不会改变整体的渐近复杂度，但它可以显著减小常数因子，从而在实践中实现更快的执行。最终的、单一的进位传播只在最顶层执行一次。这正是完全相同的理念——推迟困难的、顺序性的工作——但应用于软件算法领域，而非硬件电路。
从一个逻辑门到一个算法，进位保留算法证明了一个强大的思想：有时候，完成某件事最快的方法是巧妙地将最困难的部分推迟到最后。它在整个计算领域的应用，展示了连接晶体管物理世界与算法抽象世界的深刻原理的统一性。