补码#
参考：Two’s Complement Representation: Theory and Examples
补码（英语：2’s complement）是数字运算中的一种基本技术，它允许我们将减法运算替换为加法，常用于二进制表示有符号数的方法。补码以有符号比特的二进制数定义。
\(n\) 位二进制数 \(N\) 的补码 \(\hat{N}\) 满足：\(N + \hat{N} = 2^n\)(类比同余数概念)。
背景：使用无符号数字进行计算#
假设我们有一个加法器，它可以接收两个四位数字 \(a=a_3a_2a_1a_0\)，\(b=b_3b_2b_1b_0\) 以及一个进位输入（input carry）\(c_{in}\)，并且计算它们的和 \(a+b+c_{in}\)。如何使用加法器执行减法 \(S = a-b\)？将一个常数，如 \(M\)，加到 \(S\) 上，然后再从 \(S\) 中减去相同的常数，不会改变结果。
对于足够大的 \(M\)，有
则 (1) 可改写为
(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\) 并得到
很容易计算 \(01111_{(2)}-b\)，这是因为它就是 \(b\) 的按位反码（bitwise complement）。如果，\(b=0011_{(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\(。其中，称为补码常量(complementation constant)的 \)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)}\)，则