反码

在依赖于简单的 0 和 1 二进制状态运行的计算机数字世界中，表示正数是件简单直接的事。然而，如何高效地表示负数并进行运算，这一挑战催生了几种巧妙的解决方案。其中最早也最优雅的方案之一就是反码系统。本文将深入探讨这一迷人的方法，解决从零开始构建一个完整的有符号数算术系统的基本问题。您将探索反码背后的核心原理，从其简单的按位翻转求负，到其奇特的双零问题，以及使算术运算成为可能的巧妙的“循环进位”技术。随后，讨论将转向其在现实世界中的影响，审视其应用和跨学科联系，揭示这个抽象系统如何在早期计算机硬件中具体实现，并继续为数字设计和逻辑学提供宝贵的经验。

想象你身处一个房间，里面有一长排电灯开关。每个开关可以处于“开”或“关”的状态。这就是二进制的世界，计算机的基本语言。你能采取的最基本的操作就是沿着这排开关走下去，将每一个开关都拨到相反的状态：每一个“开”变成“关”，每一个“关”变成“开”。这种简单、普适的翻转操作，正是反码系统的核心与灵魂。

让我们从这个基本操作——​​按位取反（bitwise NOT）​​——开始。在数字逻辑的世界里，这是最简单、最原始的变换。考虑一个微控制器中的 8 位寄存器，它可能被用作一个“掩码”来控制八个不同的数据通道，其中 1 表示通道激活，0 表示通道禁用。假设掩码设置为 $01101001_2$。为了临时禁用所有活动通道并启用所有非活动通道，处理器会执行一次按位取反操作，独立地翻转每一位。0 变成 1，1 变成 0，从而将 $01101001_2$ 变换为 $10010110_2$。

这个操作有一种美妙的对称性。如果你翻转了所有的开关，然后再走一遍，把它们全部翻转回来，你将回到最初的状态。这是一种自我反转或对合（involutive）属性。应用两次 NOT 操作会返回原始数值，即 $\overline{\overline{N}} = N$。这个原理非常可靠，以至于一些简单的通信协议曾用它来进行数据完整性检查：发送方在发送消息前翻转所有比特，接收方再翻转一次以恢复原始数据。

这种优雅的按位翻转并不仅仅是个小把戏；它是构建一个有符号数表示系统的关键。早期的计算机设计师们思考：我们如何表示一个负数，比如 -25？反码系统提供了一个极为直接的答案：要找到一个负数的表示，只需从其对应的正数开始，然后简单地翻转所有位。

让我们用 8 位来尝试表示 -25。正数 $25$ 的二进制是 $00011001_2$。要找到它的负数“孪生兄弟” -25，我们应用按位取反：

就是这样。在这个系统中，$11100110_2$ 就是机器书写 -25 的方式。反过来说，如果一位“数字考古学家”在检查一台古老的 16 位机器时发现了十六进制值 $BEEF_{16}$，他们会首先注意到其最高位是 1（因为 $B_{16} = 1011_2$），这表示一个负数。为了找出它的绝对值，他们会将 $1011\ 1110\ 1110\ 1111_2$ 的所有位翻转，得到 $0100\ 0001\ 0001\ 0000_2$，即 $4110_{16}$ 或十进制的 $16656$。因此，原始值是 $-16656$。

这种方法只是表示负数的几种方式之一。将它与它的“亲戚”们进行比较是很有启发性的。例如，在一个​​原码​​（sign-magnitude）系统中，你只需取其正值（$25$ 为 $00011001_2$），然后只翻转最左边的“符号”位，得到 $10011001_2$ 来表示 $-25$。而现在标准的​​补码​​（two's complement）系统则比反码更进一步：它会翻转所有位然后再加一，得到 $11100111_2$ 来表示 $-25$。每一种系统都是对同一个基本问题的不同回答，各自带来了独特的后果。

反码的设计选择——将求负定义为简单的按位翻转——带来了一个奇特而迷人的后果，一个“机器中的幽灵”。如果我们把这个规则应用到数字零上会发生什么？

正零，自然是由全零表示的：$00000000_2$。如果我们取它的反码来寻找“负零”，我们会翻转每一位，得到 $11111111_2$。

在我们所熟知和喜爱的数学现实中，$+0$ 和 $-0$ 是同一回事。但在使用反码的机器内部，我们对同一个值有了两种不同的位模式：一个“全零”的零和一个“全一”的零。这是一个深刻的复杂问题。计算机必须不断检查一个结果是否为零，而在反码系统中，硬件逻辑必须被明确设计成能将两种模式都识别为零。这种模糊性使得比较和其他逻辑运算更加复杂和缓慢，这也是为何巧妙地避开了这个问题的补码系统最终胜出的一个关键原因。

这个“两种零”的特性直接影响了系统可以表示的数值范围。对于一个 $N$ 位系统，有 $2^N$ 种可能的模式。一种模式用于表示正零（$00...0$）。剩下模式的一半用于正数，另一半用于负数，其中包括了第二种零（$11...1$）。这导致了一个完全对称的范围。对于一个 12 位系统，最大的正数是 $0111\ 1111\ 1111_2$，即 $2^{11}-1$，也就是 $2047$。最小的负数是它的按位取反，$1000\ 0000\ 0000_2$，表示 $-(2^{11}-1)$，即 $-2047$。这个范围从 $-2047$ 到 $+2047$ 是完美平衡的，但代价就是那个奇怪的双零表示。

所以，我们有了一个表示数字的系统，它很优雅，但有一个奇特的双零问题。我们至少能用它进行算术运算吗？让我们在一个 4 位系统中尝试将两个负数相加，比如 $-2$ 和 $-3$。

• 首先，我们在 4 位反码中表示它们：

  • $+2$ 是 $0010_2$，所以 $-2$ 是 $1101_2$。
  • $+3$ 是 $0011_2$，所以 $-3$ 是 $1100_2$。

• 现在，让我们用标准的二进制加法将它们相加：

  \begin{array}{@{}c@{\,}c@{}c@{}c@{}c@{}c} & & 1 & 1 & 0 & 1 & \quad (-2) \\ + & & 1 & 1 & 0 & 0 & \quad (-3) \\ \hline & 1 & 1 & 0 & 0 & 1 & \end{array}

结果是一个 5 位的数，$11001_2$。我们的 4 位机器只能保存最右边的四位，$1001_2$。最左边的位，那个“掉出去”的 1，被称为​​进出位（carry-out bit）​​。如果我们只看这个 4 位的结果，$1001_2$，它的反码是 $0110_2$（即 6），所以 $1001_2$ 表示 $-6$。但我们知道 $-2 + (-3)$ 应该是 $-5$。答案错了！

乍一看，这似乎是一个失败。但系统的精妙之处就在于此。那个剩余的进位位不是一个要丢弃的错误；它是来自数的高位末端的一条信息，一个告诉我们下一步该做什么的信号。规则是这样的：每当加法产生一个进出位时，你必须把那个 1 加回到结果的最低有效位上。这被称为​​循环进位（end-around carry）​​。

让我们把它应用到我们的求和中：

最终结果是 $1010_2$。要看它代表什么，我们翻转各位得到 $0101_2$，也就是 $5$。所以，$1010_2$ 确实是 $-5$。魔法奏效了！

这个“循环进位”不仅仅是一个巧妙的技巧；它是一个深刻数学真理的物理体现。一个标准的 $N$ 位加法器执行的是模 $2^N$ 的算术。然而，具有双零的反码系统天然地在一个模 $(2^N-1)$ 的算术世界中运作。这两个世界几乎相同，仅相差一。同余式 $2^N \equiv 1 \pmod{2^N-1}$ 便是其数学桥梁。进出位代表了值 $2^N$，通过将其作为 1 加回来，我们实际上是强制模 $2^N$ 的硬件计算出正确的模 $(2^N-1)$ 的结果。在电路上，这异常简单：你只需将加法器的 $C_{out}$（进出位）线连接回它的 $C_{in}$（进位）端子，从而形成一个数轴“首尾相接”的反馈回路。

这个统一的系统使得其他运算，如减法，也自然而然地水到渠成。为了计算 $A - B$，机器只需计算 $A + (-B)$。它找到 $B$ 的反码（按位取反），然后使用循环进位规则执行加法。例如，在一个 8 位系统中计算 $60 - 20$，我们取 $A = 00111100_2$ (60) 和 $B = 00010100_2$ (20)。我们计算 $A + \overline{B}$：

我们有一个为 1 的进出位，所以我们把它加回去：$00100111_2 + 1 = 00101000_2$。这个结果是 $32 + 8 = 40$，完全正确。整个算术体系——求负、加法和减法——都建立在两个简单而优雅的思想之上：按位翻转和循环进位。

在纸上玩弄一个数学概念，抽象地理解其规则和属性是一回事。而看到这个概念具象化，成为计算和思考机器复杂运作机制的一部分，则是另一回事，而且要奇妙得多。我们所探讨的反码系统，就是这种从纯粹逻辑到实际应用转变的绝佳案例。尽管在现代计算机中它已在很大程度上被更精简的补码系统所取代，但它的故事并不仅仅是一个历史注脚。它在工程艺术方面给我们上了丰富而美妙的一课，揭示了当我们构建机器来执行算术时，巧妙、优雅乃至奇特的“幽灵”是如何产生的。

让我们踏上一段旅程，看看这个迷人的数字系统在何处焕发生机，从最简单的硅片到算法和抽象逻辑的宏伟架构。

机器实际上是如何“找到”一个数的反码的？答案美妙得近乎诗意：简单。要找到反码，我们“翻转”每一个位——每一个 0 变成 1，每一个 1 变成 0。在数字电子学的世界里，这个操作是由一种称为反相器（inverter）或非门（NOT gate）的逻辑门来完成的基本工作。

想象一个 4 位数沿着四条平行的导线流动。要计算它的反码，我们只需要在每条导线上放置一个非门。输出的信号集，根据定义，就是输入信号集的反码。在求负的数学运算和电路的物理动作之间，存在着完美的一一对应关系。这是第一个也是最根本的应用：思想在硅中得以显现。

反码系统的真正天才之处在于，它们提供了一种巧妙的方式，用执行加法的同一套硬件来执行减法。这在早期计算机设计中是一个里程碑式的突破，因为它极大地简化了所需的电路。工程师们不再需要构建一个独立、复杂的“减法器”单元，只需一个“加法器”和一个“反相器”即可。

规则很简单：要计算 $M - S$，机器实际上计算的是 $M + (\text{S 的反码})$。假设一个早期的微处理器需要计算 $1001_2 - 1100_2$。它首先取 $1100_2$ 的反码，即 $0011_2$。然后，它简单地将此结果加到 $1001_2$ 上，得到结果 $1100_2$。减法消失了，取而代之的是一次取反和一次加法。

但是，要让这在所有情况下都奏效，需要一种微妙而美妙的魔法。当加法从最高位产生一个进出位时会发生什么？在正常的加法中，这可能表示溢出。但在反码算术中，这个游离的位是整个事件的关键。该系统采用了一种称为​​循环进位​​的技巧。进出位不会被丢弃；它被“环绕”回来，并加到结果的最低有效位上。

考虑计算 $+50 - 35$。在 8 位反码中，这变成 $+50$ ($00110010_2$) 和 $-35$ ($11011100_2$) 模式的加法。初始的二进制加法产生的和为 $00001110_2$，并带有一个为 1 的进出位。那个‘1’是关键。它被加回到结果中，将 $00001110_2$ 变成 $00001111_2$，这正是 $+15$ 的正确表示。当两个负数相加时，比如 $-9$ 和 $-19$，同样的优雅规则也适用。初始和同样会产生一个进出位，当它被加回来时，就会产生正确的负数结果。这个循环进位就像一个微小的校正因子，仿佛来自机器算术灵魂的低语，确保逻辑完美地衔接在一起。

虽然循环进位对于加减法来说是一个美妙的解决方案，但当我们涉足其他运算时，情况就变得更加复杂了。在这里，反码的独特个性——它的怪癖和精妙之处——才真正开始显现，为有抱负的数字架构师提供了深刻的教训。

​​关于捷径的提醒​​

在数字设计中，工程师们喜欢高效的技巧。最常见的技巧之一是使用移位来执行乘以或除以二的幂次。一次逻辑左移（将所有位向左移动一个位置，并在最后一位填充一个 0）对于无符号数来说相当于乘以二。但我们能在反码系统中使用这个技巧吗？

让我们尝试用两次逻辑左移来将 $-1$ 乘以四。在 4 位反码中，$-1$ 是 $1110_2$。将其左移两次得到 $1000_2$，它代表 $-7$。但正确答案当然是 $-4$。这个捷径惨败。为什么？逻辑左移不尊重符号位。它盲目地将位移出，可能将一个负数变成正数，或破坏其值。这揭示了一个关键原则：算法和硬件技巧并非普遍适用；它们必须根据其操作的数字系统的特定规则量身定制。

​​机器中的幽灵：负零​​

也许反码最著名的特性是它对零的双重表示。有“正零”($0000...0_2$) 和“负零”($1111...1_2$)。虽然它们的数学值相同，但它们是不同的位模式。这种二元性可能导致奇怪而奇妙的结果。

考虑整数 $-1$，在 8 位中表示为 $11111110_2$。如果我们执行一次算术右移，它会将所有位向右移动但保留符号位，会发生什么？最右边的 0 被丢弃，所有其他位向右移动，最左边的位（符号位，一个 1）被复制到新空出的位置。结果是 $11111111_2$——负零。一个本应近似于除以二的操作，却将 $-1$ 变成了 $0$。这个怪癖是设计师最终偏爱补码的一个主要原因，因为补码对零只有一个单一、明确的表示。

​​构建智能算法​​

尽管有其古怪之处，反码是许多早期计算机算术逻辑单元（ALU）的基础。工程师们学会了利用其特性来构建复杂的算法。例如，乘法不是一步完成的。它通常是通过一系列的加法和移位来顺序实现的。为了计算 $(-5) \times (+3)$，机器会加载 $-5$ 和 $+3$ 的表示，然后在乘数位的引导下，重复地将被乘数加到一个累加和上，并在每一步都对结果进行移位。反码加法的基本操作，及其循环进位，成为这个更复杂过程的原子构建块。

工程师们甚至将像 Booth 算法这样的高效算法应用于反码机器。Booth 算法通过分组处理位来加速乘法。然而，它最初是为补码设计的。直接将其应用于反码数会得到错误答案。解决方案是什么？一个美妙的洞见。工程师们意识到，标准的 Booth 算法作用于一个负的反码数 $Y$ 时，实际上计算的是与 $Y-1$ 的乘积。因此，为了得到正确答案，需要一个最终的校正步骤：只需将乘数 $M$ 加回到结果中。这是工程创造力的典型例子：当一个强大的工具不完全适用时，你不会丢弃它；你会为它制造一个适配器。

反码的影响超出了纯粹的算术，连接到更广泛的计算机科学和逻辑领域。

​​作为观察者的机器：自动机理论​​

计算机中的任何数字，其核心都只是一种位模式。4 位反码表示的 $-3$ 是 $1100_2$。这不仅仅是一个数字；它是一个序列。我们可以设计一个称为有限状态机（FSM）的数字电路来“监视”一连串输入的位，并在看到模式 $1100$ 的瞬间举起一个标志。这样的序列检测器是网络、数据处理和控制系统中的基本组件。这个应用表明，一个数字系统产生的特定位模式对模式识别和时序逻辑的设计有影响，将计算机算术的世界与自动机理论领域联系起来。

​​编码新现实：三元逻辑一瞥​​

也许最能拓展思维的应用是概念性的。我们能用一个二进制系统来表示二进制数以外的东西吗？考虑一个假设的处理器，它被设计用于处理一个具有真、假和未知三种状态的三值（三元）逻辑系统。一位架构师可以巧妙地将 4 位模式分配给这些状态——例如，假 = 0000，未知 = 0011，真 = 1111。

这个特定（尽管是假设的）选择的绝妙之处在于，复杂的三元与逻辑规则现在可以通过单个标准的按位与运算来实现。例如，真 与 未知 应该等于 未知。在我们的表示中，这是 1111 & 0011，它确实产生了 0011！。这展示了一个深刻的原则：我们使用的位模式是一种编码形式，通过巧妙的编码方案，我们可以让简单的二进制硬件执行一个完全不同、更复杂的系统的逻辑。

我们对反码世界的探索，从卑微的非门一直延伸到编码三元逻辑的抽象之美。我们看到了它对减法的优雅解决方案，它在简单捷径上的危险陷阱，以及工程师们为驯服其怪癖而设计的巧妙修复方法。反码的故事有力地提醒我们，在计算的世界里，数学不是一项旁观者的运动。一个抽象系统的每一条规则、每一个属性、每一个怪癖都有真实、有形的后果，为那些构建塑造我们世界的机器的人们，创造了一幅充满了挑战和机遇的丰富画卷。