玻尔百科从最简单的计算器到最强大的超级计算机，每台数字计算机的核心都具备执行算术运算的能力。虽然加法常常成为焦点，但减法也是同样基础的操作。但是，一台由简单的开/关构成的机器，实际上是如何执行像 这样的操作呢？答案始于一个出人意料地简单而优雅的数字逻辑电路：半减器。这个组件解决了该问题最基本的形式——将一个比特从另一个比特中减去——并由此为所有二进制减法提供了基础构建模块。
本文将剖析半减器，揭示支撑现代计算的逻辑。在第一章“原理与机制”中，我们将探索赋予半减器功能的那些基本逻辑门，了解其局限性如何催生出功能更强大的全减器，并揭示加法与减法之间深刻的统一性。随后，在“应用与跨学科联系”一章中，我们将展示这些简单的模块如何组装成强大的算术单元，如何被创造性地应用，甚至如何用于弥合具体硬件与计算机科学抽象理论之间的鸿沟。
好了，我们来深入探讨一下。我们已经讨论了半减器的用途，但它究竟是如何工作的？其内部机制是怎样的？我们又如何从这个简单的构建模块发展到能执行复杂算术运算的部件？这才是真正有趣的地方，在这里我们将看到数字逻辑不仅仅是规则的集合，更是一个由优美、互联的思想构成的乐园。
让我们从你能问的最基本的问题开始：如何从一个比特中减去另一个比特？只有四种可能性，你早已烂熟于心，即使你以前没有这样想过。我们称这两个比特为 （被减数）和 （减数）。
所以，一个执行这种运算的电路，即半减器，需要两个输出：差值（）和借位输出（）。让我们将我们的发现制成表格：
| X | Y | 差 (D) | 借位 () |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
仔细看 列。它看起来熟悉吗？这与异或门 (XOR) 产生的模式完全相同。当输入不同时，输出为 ；当输入相同时，输出为 。所以，我们的差值逻辑很简单：
现在，再看 列。我们只在一种特定情况下产生借位：当我们试图从 中减去 时。换句话说，当 为 且 为 时。用逻辑门的语言来说，就是：
就是这样！这就是半减器的全部“原理与机制”。两个简单的逻辑门赋予了我们减去两个比特的能力。它优雅、简约，但有一个关键的局限性。那个 信号必须有去处。一个更复杂的减法问题中的下一位需要知道我们向它借了位。我们简单的半减器可以产生借位，但它没有输入端来接收借位。
我们如何处理来自前一级的输入借位呢？我们需要一个功能更强的电路，一个全减器。这个设备需要三个输入：被减数 、减数 和一个输入借位（）。任务是计算 。
现在，我们可以直接为这三个输入画一个有八行的巨大真值表，然后从头推导逻辑。这样做完全可行！你会发现最终的差值 是 ，而最终的借位输出 则有一个更复杂的表达式：。
但有一种更优美、更直观的思考方式，一种揭示了模块化设计力量的方式。为什么不使用我们已经理解的半减器呢？我们需要计算 。让我们分两步来做。
首先，计算 。 我们可以将 和 输入到我们的第一个半减器中。它会产生一个中间差值，我们称之为 ，以及一个中间借位 。
接着，从该结果中减去 。 我们取中间差值 ，并从中减去输入借位 。我们可以为此使用第二个半减器！它的输入是 和 。它将产生我们最终的差值 ，以及第二个借位信号 。
最终的差值很容易计算： 。
但最终的借位输出呢？我们的全减器应该在什么时候向下一级发出借位信号？如果第一次减法需要借位（即 ），或者第二次减法需要借位（即 ），那么就需要一个借位。我们所要做的就是用一个或门将这两个中间借位信号组合起来。
这就是从我们的模块化设计中自然得出的逻辑。通过一点布尔代数，你可以证明这个表达式在逻辑上与我们从那个大真值表中得到的表达式是相同的。这是一个绝妙的结果！它表明我们可以通过巧妙地组合更简单的电路来构建复杂的电路，就像用乐高积木搭建城堡一样。我们还可以用一个译码器和一些或门来实现整个电路，证明它只是其基本最小项的特定组合。
此时，你可能认为加法器和减法器是两种不同的东西。你需要一套芯片用于加法，另一套用于减法。但如果我告诉你它们几乎是同一种东西呢？一个全加器只需几个反相器就可以变成一个全减法器？这是科学中那些看似不同的想法被揭示为同一枚硬币的两面的时刻之一。
让我们看看全加器的逻辑。它计算 并产生一个和（）和一个进位输出（）。
现在比较和与差的输出： 它们的结构完全相同！三输入异或运算是两者的核心。
当我们研究借位和进位逻辑时，神奇之处就显现了。我们并非要重新设计一个电路，而是要看看能否通过巧妙地连接一个全加器的输入来产生全减法器的输出。
如果我们这样连接全加器会怎样：
让我们看看加法器的输出会怎样。和输出变为： 在单比特布尔代数中，有一个恒等式：。应用两次该恒等式： 这正是全减法器的差值输出 ！
现在是真正令人惊叹的部分。加法器的进位输出呢？通过我们巧妙的输入，它变为： 这看起来和我们的借位输出表达式完全不同。但看看如果我们对这个信号进行反相会发生什么。使用德摩根定律， 简化为： ...经过一番代数展开后，变成... 这正是我们的借位输出 的表达式！
这意义深远。通过在输入端 和 加两个反相器，在进位输出端加一个反相器，一个全加器就变成了一个全减法器。减法不是一个新的基本操作；它只是伪装起来的加法。正是这种潜在的统一性使得物理学和工程学如此优美。自然是经济的；它会重复利用好的想法。
到目前为止，我们的逻辑一直是 0 和 1 的完美、永恒之舞。但我们构建的电路存在于现实世界中，一个充满物理约束的世界。导线有长度，逻辑门转换需要时间。
当一个门的输入改变时，输出不会瞬时改变。存在一个微小的传播延迟。对于单个门，这个延迟可能只有几纳秒，但在复杂电路中，这些延迟会累积。从任何输入到输出的最长延迟路径被称为关键路径，它决定了电路的最高速度。
让我们比较一下加法器进位输出和减法器借位输出的关键路径。
请注意，减法器的逻辑需要在输入 上进行一次反相。这意味着来自 的信号必须先通过一个非门，然后才能到达与门。这给路径增加了一个额外的门延迟。因此，在其他条件相同的情况下，减法器的借位输出信号比加法器的进位输出信号需要稍长的时间才能稳定下来。这不仅仅是一个微不足道的好奇点；它是一个可能限制微处理器时钟速度的关键因素。
这些不同的路径延迟也可能导致其他问题。想象一下一个输入发生变化，逻辑中的一条路径比另一条快。在瞬间，门的输入可能是一个意想不到的组合，导致输出端出现一个短暂的、不希望有的脉冲，即毛刺。这被称为险象。例如，在借位输出逻辑的某些实现中，当其他两个输入保持不变时改变一个输入，可能会导致输出瞬间降至 0，尽管逻辑表显示它应该保持为 1。一个优秀的设计师必须预测并消除这些险象，以确保电路的可靠性。
当东西就是坏了的时候会发生什么？一根导线可能短路接地，造成固定为0故障。工程师必须像侦探一样，找出哪种输入组合会揭示这个故障。例如，如果一个全减法器的 线固定为 0，对于像 或 这样的特定输入，电路将产生错误的借位输出，但对于其他输入则工作正常。这种分析对于测试和确保我们制造的芯片确实能按其优美的逻辑所说的那样工作至关重要。
从一个简单的 问题出发，我们经历了模块化设计，揭示了加法和减法之间深层的统一性，并窥见了速度和可靠性的现实挑战。半减法器不仅仅是一个组件；它是一段进入计算核心的迷人旅程的起点。
在剖析了半减器并组装了其功能更强大的近亲——全减器之后，我们可能会满足于对其内部机制的理解，而将这些工具放回工具箱。但这就像学会了音阶却从未演奏过一首乐曲。这些简单电路的真正魔力，其深刻之美，并非体现在它们是什么，而在于它们能做什么——更重要的是，在于它们使我们能够构建什么。从一个只知道 的逻辑门，到一个能计算行星轨迹的处理器，这是一段关于层次、优雅和抽象的故事。现在，让我们踏上这段旅程。
第一个，也是最明显的挑战是规模问题。我们的世界不是由单个比特描述的，而是由巨大的数字描述的。我们如何从一个1位减法器发展到一个能处理现代计算机64位数字的电路？
最直接的方法就是完全模仿我们用纸笔计算的方式。在减去多位数时，我们从右到左，逐列进行。如果我们需要从一个较小的数字中减去一个较大的数字（例如，），我们从左边的列“借位”。我们可以构建一个数字电路来模仿这个过程。我们可以将我们的1位全减法器串联起来，其中一个级的borrow-out（借位输出）成为下一个更高有效位的borrow-in（输入借位）。这种设计，被称为脉动借位减法器，是模块化设计的完美典范。一个复杂的4位、8位，甚至64位减法器，就是通过简单地复制和连接一个单一、易于理解的组件来构建的，就像用相同的砖块砌墙一样。借位信号在链中“脉动”传播，从最低有效位到最高有效位，将必要的信息从一列传递到下一列。
这很实用，但它优雅吗？物理学家或工程师总是在寻找更深层的统一性、更高效的方法。当加法和减法这两种运算感觉如此相关时，为什么还要为它们分别设置电路呢？在这里，我们发现了数字设计中最优美的技巧之一。减法可以通过一种叫做二补数的概念转化为加法。要计算 ，我们可以转而计算 。在二进制中， 的二补数表示是通过将 的所有位取反，然后加 1 得到的。
这为我们提供了一个绝妙的想法，来构建一个组合的加/减法器单元。我们需要一种方法，要么让输入 不变地通过（用于加法），要么将其反相（用于减法）。异或门是完成这项工作的完美工具！一个异或门的一个输入连接到控制信号 ，它就像一个可控反相器：如果 ，则 ；如果 ，则 。然后我们可以将这个结果输入一个全加器。但是二补数的“+1”部分怎么办呢？我们可以简单地将加法器的初始进位输入设置为我们的控制信号 。当 （用于加法）时，进位输入为 0。当 （用于减法）时，进位输入为 1。通过一个全加器和一把异或门，我们创造了一个单一、紧凑的电路，可以执行两种基本的算术运算，构成了计算机算术逻辑单元（ALU）的核心。
全减法器，就像一个多才多艺的演员，其作用不限于其名义上的角色。其底层的逻辑——异或和与运算的复杂相互作用——可以被利用于其他，有时甚至是令人惊讶的功能。通过操纵其输入，我们可以引导它执行新的任务。
例如，我们可以设计一个“条件自减器”，一个仅当控制信号 激活时才从数字 中减去 1 的电路。否则，它应该只是让 不变地通过。这在编程循环和计数器中是常见的需求。我们可以用一个全减法器来实现这一点。通过巧妙地连接输入——将被减数设置为 ，减数设置为控制信号 ，初始输入借位设置为 0——电路自然地执行 。如果 ，它计算 。如果 ，它计算 。这展示了硬件设计的一个基本原则：从简单的、功能固定的模块创建灵活的、可编程的组件。
创造的潜力不止于此。如果我们想计算两个单比特的绝对差 呢？这个操作等同于异或函数，因为当 时 为 1，当 时为 0。乍一看，这似乎与减法无关。然而，通过一些逻辑上的游戏，我们可以使用一个全减法器来实现这一点。通过以一种非直观的方式连接输入，然后将减法器的两个输出——差和借位——与一个最终的逻辑门结合，我们可以精确地产生我们需要的异或函数。这就像一个物理学家在一个方程中发现了意想不到的对称性。它表明，对底层原理的深刻理解使我们能够看到那些从组件名称中不那么明显的联系和构建功能。
到目前为止，我们的设计都是“并行”的。一个4位脉动借位减法器使用四个全减法器来同时计算所有四个输出位（除去借位脉动传播的微小延迟）。这很快，但可能需要大量硬件。如果我们受空间而非时间的限制呢？
这引出了一种完全不同的计算哲学：串行方法。我们可以使用单个全减法器，一次处理一个比特，而不是同时处理所有比特。想象有两长串比特，即我们的数字 和 ，每个时钟周期各取一个比特送入我们单个的减法器。减法器计算该位置的差值比特。但是借位怎么办？当前周期的借位输出必须被“记住”，以便在下一个周期用作输入借位。这个记忆的角色由一个简单的1位存储元件——D型触发器——来扮演。每次计算后，借位输出被触发器捕获，为时钟的下一个节拍做好准备。这种串行减法器用时间（多个时钟周期）换取硬件（多个减法器），这是工程师们不断权衡的一个基本取舍。
从并行硬件到时序过程的转变，将我们带到了计算机科学中一个深刻思想的门前：有限状态机（FSM）。串行减法器是有限状态机的一个物理实现。它有有限数量的状态（在这种情况下，只有两个：“不需要借位”或“需要借位”），并根据当前输入（来自 和 的比特）在这些状态之间转换。机器的输出（差值比特）是其状态和输入的函数。
计算机科学家已将此概念形式化为不同的模型，例如米利型状态机（Mealy machine），其输出取决于当前状态和当前输入；以及摩尔型状态机（Moore machine），其输出仅取决于当前状态。我们的串行减法器可以用其中任何一种模型完美地建模，为一个可能抽象的计算理论提供了具体、物理的例子。它构筑了一座美丽的桥梁，表明二进制算术的逻辑和抽象机器的理论是同一枚硬币的两面。
我们已经从单个逻辑门到多位单元，从并行到串行架构，从具体电路到抽象状态机。最后一步是看到这些减法器在其自然栖息地中的样子：作为执行复杂算法的大型机器中的齿轮。
考虑寻找两个数的最大公约数（GCD）的问题。历史上最古老的算法之一是欧几里得算法，但一个对二进制数更友好的版本是 Stein 算法。它依赖于一套简单的规则，包括检查数字是奇数还是偶数（检查最低有效位 LSB），除以二（一个简单的位移操作），以及至关重要的减法。
一个为执行此算法而设计的专用协处理器将包含我们的算术单元作为核心组件。一个串行数据路径可以使用串行减法器、用于保存数字的移位寄存器以及用于协调操作序列的控制逻辑来实现 Stein 算法。在这里，减法器不再是主角；它是一个可靠的工人，被更高层的控制器调用，以完成其特定任务，作为更宏大计算策略的一部分。
于是，我们的探索回到了原点。诞生于几个与门、或门和非门的半减法器的简单逻辑，是种子。它成长为全减法器。这些反过来又被组装成算术逻辑单元（ALU），被重新用于创造性逻辑，在时间上伸展为串行处理器，并被抽象为有限状态机。最后，它们成为驱动复杂算法执行的谦逊而不可或缺的组件。其美妙之处在于这个宏伟的层次结构——一个计算的宇宙，全都建立在“一减一等于零”这个简单而优雅的真理之上。