为了表示负数，世界上大部分的计算机系统都采用了补码来表示整数。补码对应的英文原文是two’s complement，其中的单词 two 有什么含义呢？本文就来探讨一下补码的原理。

补数

我们都知道CPU内部使用加法器来实现整数加法。那减法运算呢，也有一个专门用作减法运算的减法器吗？其实不然，在模算数系统下减法可以转换为加法。

在数学和计算中，补数法是一种对正整数和负整数的对称范围进行编码的技术，使它们可以在整个范围内使用相同的算法（硬件）进行加法运算。对于给定的位数，可能表示的数的一半编码正数，另一半表示它们各自的的加法逆元。这对互为加法逆元的数称为补数。

CPU的加法器是有限域加法，例如，int + int 的结果仍然是int，是一种模算数系统。

在有限正整数域 $M = \{x|0 \leq x < m, x \in N\}$ 中，若 $a + b = M$ 其中 $a \in M, b \in M$ ，则 $m \bmod m = 0 = a + b$ ，而且 $b \equiv -a \pmod m$。也就是说在数域 $M$ 中 $b$ 可以用来表示 $-a$ ，因此 $x - a = (x + b) \bmod m$，这样减法就转换成了加法，也得到了负数的表示方法。

对于 $n$ 位 $r$ 进制数，规定

  • $r^{n}-a$ 是 “ $r$ 进制数 $a$ 的关于基数的补数（$r$ 的补数）”
  • $r^{n}-1-a$ 是“ $r$ 进制数 $a$ 的关于减基数的补数（$r - 1$ 的补数，简称减补数、侪补数）”

$ r^n $ 使用 位置记法（positional notation） 记作 $ 1\underbrace{0000\cdots0}_{n位} $；显然有$ r^n - 1$ 使用位置记法记作 $ \underbrace{(r-1)|(r-1)|(r-1)|\cdots|(r-1)}_{n位(r-1)} $。 故 $ r^n -1 = \sum_{i=0}^{n-1}(r-1)r^{i} $，两边同时加$1$，可得 $ r^n = \sum_{i=0}^{n-1}(r-1)r^{i} + 1 $。

有了上面知识，我们来讨论如何使用补数法将减法运算转换为加法运算。

基数的补数(radix complement)

数 $a$ 是 $r$ 进制数（即基数为r），位数为 $n$，将 $a$ 按其各个数位展开有

$a = a_{n-1}r^{n-1} + a_{n-2}r^{n-2} +...+ a_0r^0 = \sum_{i=0}^{n-1}a_ir^{i}$

根据基数的补数定义，有

$$ \begin{align} a + b &= r^{n} \\ \sum_{i=0}^{n-1}a_ir^{i} + b &= r^{n} \\ &= \sum_{i=0}^{n-1}(r-1)r^{i} + 1 \\ b &= \sum_{i=0}^{n-1}(r-1)r^{i} - \sum_{i=0}^{n-1}a_ir^{i} + 1 \\ &= \sum_{i=0}^{n-1}(r - 1 - a_i)r^i + 1 \end{align} $$

$r$ 的补数计算方法，即用 $r - 1$减去 $a$ 的每一位后再加1。

二进制下，基数为2，此时基数的补数就是two’s complement（二补数），即我们通常说的补码。不难发现，二进制下$\underbrace{111\cdots1}_{n位} - a_{n-1}a_{n-2} \cdots a_0$的结果等于对 $a$ 按位取反的结果，所以二进制下求一个数的补码只需对其按位取反再加1即可。

已知 $b$ 是 $a$ 的基数的补数。如果要计算 $c -a$ 时，将 $-a$ 代入其中

$$ \begin{align} -a &= - r^{n} + b \\ c - a &= (c - r^{n} + b) \bmod r^{n} \\ &= c + b \end{align} $$

也就是说减法运算可以转换加法运算，只需得到补数相加即可

减基数的补数（diminished radix complement）

根据减基数的补数定义，有

$$ \begin{align} a + b &= r^{n} - 1 \\ \sum_{i=0}^{n-1}a_ir^{i} + b &= r^{n} - 1 \\ &= \sum_{i=0}^{n-1}(r-1)r^{i} + 1 - 1 \\ b &= \sum_{i=0}^{n-1}(r-1)r^{i} - \sum_{i=0}^{n-1}a_ir^{i} \\ &= \sum_{i=0}^{n-1}(r - 1 - a_i)r^i \end{align} $$

因而，用 $r - 1$ 减去 $a$ 的每一位就能得到了数 $a$ 的 $r -1$ 的补数。对于二进制数，求它的一补数（one’s complement，即反码）只需对其按位取反即可。

接下来看看如何使用用减补数表示法将减法转换为加法

$$ \begin{array}{rll} a + b &= r^n - 1 \\ c - a &= [c - (r^n - 1 - b)] \bmod (r^n - 1) \\ &= [c + b - (r^n -1)] \bmod (r^n - 1) \\ &= (c + b) \bmod (r^n - 1) \\ \\ 分情况讨论:& \\ 1 . 若c + b < r^n - 1 & (c + b) \bmod (r^n - 1) &= c + b \\ 2 . 若c + b = r^n - 1 & (c + b) \bmod (r^n - 1) = 0 = r^n - 1 &= c + b\\ 3 . 若c + b > r^n - 1 & (c + b) \bmod (r^n - 1) &= c + b - (r^n - 1) \\ &&= (c + b - r^n) + 1 \\ \\ 综上 \quad c- a &= \left \{ \begin{array} {l} c + b &c + b \leq r^n - 1 \\ (c + b - r^n) + 1 & c + b > r^n - 1 \end{array}\right. \end{array} $$

当 $c + b > r^n - 1$ 时，显然 $c + b$ 有进位，此时结果中的1可以认为是进位。不难看出，两种情况可以统一使用一种计算方法，即 $c + b + 进位$

下面举个例子，4位二进制数，用反码计算 $-1 - 5$

$$ \begin{array}{rr} 1110 & -1 \\ +1010 & -5 \\ \hline 11000 \\ \hline 1000 \\ 1 \\ \hline 1001 & -6 \end{array} $$

所以用反码也能合理地表示负数，虽然会出现2个为0的值。据说历史上曾经有过使用反码来表示负数的计算机。

结论

利用补数（不管是基数的补数还是减基数的补数）就能将减法运算转换为加法运算。在二进制下，利用补码和反码都可以仅使用位运算和加法器实现减法。

参考资料

https://en.wikipedia.org/wiki/Method_of_complements

https://zh.wikipedia.org/wiki/模算數