补码

补码#

参考：Two’s Complement Representation: Theory and Examples

补码（英语：2's complement）是数字运算中的一种基本技术，它允许我们将减法运算替换为加法，常用于二进制表示有符号数的方法。补码以有符号比特的二进制数定义。

$n$ 位二进制数 $N$ 的补码 $\hat{N}$ 满足： $N + \hat{N} = 2^{n}$ (类比同余数概念)。

背景：使用无符号数字进行计算#

假设我们有一个加法器，它可以接收两个四位数字 $a = a_{3} a_{2} a_{1} a_{0}$ ， $b = b_{3} b_{2} b_{1} b_{0}$ 以及一个进位输入（input carry） $c_{i n}$ ，并且计算它们的和 $a + b + c_{i n}$ 。如何使用加法器执行减法 $S = a - b$ ？将一个常数，如 $M$ ，加到 $S$ 上，然后再从 $S$ 中减去相同的常数，不会改变结果。

(1)#

S = a + M - b - M

对于足够大的 $M$ ，有

(2)#

B = M - b > 0

则 (1) 可改写为

(3)#

S = a + B - M

(3) 需要一次加法和一次减法运算。此外，还需要计算另一个减法，即 (2)。看起来我们把事情变得更复杂了，因为 $S = a - b$ 只需要一次减法运算，而 (3) 需要一次加法和两次减法运算！然而，注意到 (3) 所需的两个减法有一个共同点：这两个减法都涉及到一个公共操作数 $M$ 。这使我们想到，也许我们可以找到合适的 $M$ ，使得我们可以简化 (2) 和 (3) 的减法。如果可能的话，这将允许我们使用 (3) 将减法替换为加法。所以问题仍然是：对于常数 $M$ ，什么是一个合适的值？正如我们将在下一节中看到的那样， $M = 2^{k}$ 被证明是适用于 $k$ 位数字的合适值。

假设 $b$ 是一个四位数字，我们来测验减法 $M - b$ 。使用 $M = 10000_{(2)} = 16_{(10)}$ 化简减法。这种简化是可能的，因为我们可以将 $M$ 表示为 $(M - 1) + 1$ 并得到

B = 10000_{(2)} - b = (01111_{(2)} - b) + 00001_{(2)}

很容易计算 $01111_{(2)} - b$ ，这是因为它就是 $b$ 的按位反码（bitwise complement）。如果， $b = 0011_{(2)}$ ，则

B = (01111_{(2)} - 0011_{(2)}) + 00001_{(2)} = 01100_{(2)} + 00001_{(2)}

正如你所看到的，括号内的减法是 $b$ 的按位反码。因此，要执行减法 $M - b$ ，我们只需要找到 $b$ 的按位反码，然后将 $00001_{(2)}$ 加到结果中。我们将在本文后面看到，从实现的角度来看，将 $00001_{(2)}$ 加到一个数的按位反码上是一项简单的任务。这样 (3) 只剩 -M 需要处理。其实只需要丢弃第 $5$ 位上的位。这实际上等同于执行模 $M$ 计算，这意味着我们将计算结果限制在小于或等于 $M - 1$ 的范围内。

小技巧

以上讨论可以总结如下：如果 $a$ 和 $b$ 是两个 $k$ $位数字，则可以通过将$ M-b $加到$ a $，并丢弃第$ k+1 $位来计算减法$ a - b $。其中，称为补码常量 (c o m p l e m e n t a t i o n c o n s t a n t) 的$ M $等于$ 2^k$。

在模 $M$ 算术中， $M - b$ 充当 $b$ 的相反数，并称为 $b$ 的二进制补码（ $M = 2^{k}$ ）。这种相反的性质是显而易见的，因为将 $b$ 加到 $M - b$ 上会得到 $M$ ，这在模 $M$ 算术中等于 $0$ 。基于这个想法，我们可以定义 $b$ 的相反数为 $M - b$ 。如上所述，我们可以通过首先计算一个数的按位反码，然后将 1 添加到结果来计算该数的二进制补码。

假设我们正在处理无符号的四位数字。使用二进制补码表示法，有 $a = 1011_{(2)} = 11_{(10)}$ ， $b = 0110_{(2)} = 6_{(10)}$ ，则

a - b = 0101_{(2)} = 5_{(10)}

补码

目录

补码#

背景：使用无符号数字进行计算#