为了表示负数，世界上大部分的计算机系统都采用了补码来表示整数。补码对应的英文原文是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}-a-1\) 是“ \(r\) 进制数 \(a\) 的关于减基数的补数（\(r - 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)^{i} + 1 \\ b &= \sum_{i=0}^{n-1}(r-1)^{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)^{i} \\ b &= \sum_{i=0}^{n-1}(r-1)^{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 \leq r^n - 1 & (c + b) \bmod (r^n - 1) &= c + b \\ 2. 若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} \]

参考资料

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

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