补码

程序设计课对补码一笔带过，然而我想，这样反直觉的东西是需要细细思考和理解的，翻阅网上的文件，都不能令我满意，于是作此文，探讨补码的本质。本文从零开始，不作任何先验的假设

1. 如何表示无符号整数？

我们知道，用二进制形式表示无符号整数是简单，直观，自然的。但是，理解这种 “简单，直观，自然” 对接下来探讨有符号整数有很大的好处。

先来厘清自然语言带来的含混之处：

“无符号整数“ 是一个形如 ${x \in N ∣ x < m}, m \in N^{+}$ 的集合 $A$ ，这总是一个有限集， $| A | = m$ （当然，通过增加 $m$ ，实际上可以包括任意的整数，一个简单的极限过程）
“二进制形式” 是由相同长度的的所有 "0-1" 串构成的集合 $B$ ，若长度为 $n$ ，则 $| B | = 2^{n}$ （暂时不使用“二进制数”的概念，因为本文的讨论先于它）
“表示” 一词的确切含义是，能够构造两个集合之间的双射（当然，出于实际考虑，这个双射需要是可计算的，可计算这个条件非常容易满足，于是在下文忽略）

我们知道，两个有限集合存在双射，当且仅当它们的元素数量相同，那么只需要 $m = 2^{n}$ ，就一定存在用 $B$ 表示 $A$ 的方法，特别地，一个自然的方法如下：

不妨设 $n = 4$ ，由于自然数由皮亚诺公理定义，“后继”的概念十分根本，所以我们按照后继的顺序依次确定其二进制表示：

先确定 (0000) 表示 0，因为它们如此相像
然后，(0001) 表示 1，因为在熟悉的十进制中，(0001) 恰恰就是 1，
此时已经有了一种倾向：保持左边尽可能都是 0，秉持这一信念，就应当用 (0010) 或者 (0011) 来表示 2，以使得最左边只有 2 个 0，由于前者看起来“更小”，于是我们选择 (0010)，而把 (0011) 留给 3 ......
最后，只剩下了 (1111) 与 15，配为一对

事实上，我们所有人正是使用这种方法表示无符号整数的，但要注意到，存在其他不同的可能，例如，用 (0000) 表示 15，(0001) 表示 14 ...... 最一般的是，我们随机确定 $B$ 的一个排列，然后将排列中的每一个元素和它的序数（从0开始）对应起来

一般地，用 $B$ 表示 $A$ 的方法有整整 $m!$ 种，然而我们都选取了最 “简单，直观，自然” 的方法，这提示我们，最终确定某一种表示，不是因为它不可替代，而是因为它有某些更优秀的性质，对于本节的例子，优秀性有多种体现，我们暂且只指出最重要的一项：容易定义 $B$ 上的后继运算使之与 A 同构！

更严格地说，设 $B$ 到 $A$ 的双射为 $f$ ， $A$ 上的后继运算为 $+ +$ ， $B$ 上的后继运算为 $* *$ ，如果 $\forall b \in B : f (b * *) = f (b) + +$ ，那么说这是一个同构

凭借已经学习的知识，我们知道，” $* *$ “ 运算就是二进制上的自增运算，而 $f$ 实际上是对同一个数不同进制的转换，在这一观点下，这种同构就是显然成立的

但正如前文所说，在此使用进制的观点是理解上的循环，违背了从零开始设计的原则，所以，让我们重新理解为什么 **"容易定义 $B$ 上的后继运算使之与 A 同构" **

实际上，这是因为

f (b * *) = f (b) + + ⟺ f^{- 1} (f (b * *)) = f^{- 1} (f (b) + +) ⟺ b * * = f^{- 1} (f (b) + +)

因此，只需保证最右边的等式恒成立！由于我们正是按照后继的顺序为自然数 $a$ 安排二进制表示 $b$ ，因此只需要将 $b * *$ 定义为下一个被安排的二进制形式即可，如果你还记得我们安排二进制形式的原则是 保持左边尽可能都是 0，这实际上意味着相邻的二进制形式在 "0-1" 串的意义上很邻近（因为它们被“挤压”在了一起），这实际上就是说， $* *$ 运算是容易定义和计算的，事实上，使用一系列基本的逻辑门即可！

我们仍然以 $n = 4$ 的情况为例，之前的讨论忽略了边界情况：当 $a = 15$ 时，由于 $16 \notin A$ ，不能将 $a + +$ 定义为 16，当然，我们都学习过模和同余，所以把 $15 + +$ 设置为 0 是无比自然的，这样就保持了 $(a + +) - a \equiv 1 (m o d n)$ 类似地，将 (1111) $* *$ 定义为 (0000)，这样就保持了同构！巧妙的是，这恰恰是计算机中溢出的自然结果，所以 $* *$ 容易计算的性质被神奇地保持了！

至此，我们已经理解了为何这种司空见惯的表示方法恰恰具有关于后继运算的同构性以及容易计算性（考虑自由度，可知这描述的是一件事，而不是两件事），可为什么这一性质就是尤其重要的？

我们先暂且把计算机理解成只用于处理外部整数的机器，它接收整数输入，转换为二进制形式存储和运算，输出整数。那么我们最关心的一点就是二进制运算的速度。

熟知，根据皮亚诺公理，自然数的所有其他运算都由后继运算定义，这些运算实际上的计算方式也和后继息息相关，所有其他运算都由后继运算定义 ，这是至关重要的，因为这说明后继运算上的同构能够保持到所有其他运算上，于是我们为了说明某种运算仍然保持同构，只需要说明 $B$ 上的该种运算符合 $B$ 上的后继运算即可！

一方面，这以坚实的理论基础揭示了为什么后继运算尤为重要，特别地，为什么后继运算的计算速度尤为重要；另一方面，我们在下文只需要说明 $B$ 与 $A$ 关于后继运算同构，就可以放心地把视线聚焦在 $B$ 上设计运算，而不用再担心其正确性了。

2. 如何表示有符号整数？

本文几乎一切理论基础几乎都在第一节建立起来了，因此原先复杂的补码也将变得容易理解，收获成果的时间到了！

如果参照第一节，现在应当给出对名词的定义，但这里并不一样。称有符号整数是集合 $C$ ，我们只能知道 $C$ 是一个可能包含负数，零和正数的整数集合（用集合的语言，写作 $C \in 2^{Z}$ ），然而现实中的 $C$ 还有其他性质！

我们考虑有符号整数的功能性，这是另一个先验性的假设，可以想想，一个包含很多正数，很少负数的集合是没有意义的，因为最基本的求相反数运算都不能定义，这说明 $C$ 中的正数与负数需要大致平衡，又因为需要 $B$ 与 $C$ 的双射， $| C |$ 为偶数，除去零后不能完全平衡，故设 $C$ 为形如 ${x \in Z ∣ - 2^{k} \leq x < 2^{k}}, k \in N$ 的集合

有了第一节的经验，我们现在有明确的目标：寻找 $B$ 到 $C$ 的双射，满足关于其同构的 $C$ 上的后继运算 $* *$ 是容易计算的。

显然， $B$ 是长度为 $k + 1$ 的 “0-1”串，那么一个自然的想法是效仿第一节中的构造过程，按照大小顺序为 $C$ 中元素分配二进制表示，即 $B$ 中的元素，不失一般性，我们令 $k = 4$ ，于是 $C = [- 16, 15] \cap Z$ ：

先确定 (00000) 表示 -16
然后，(00001) 表示 -15
...... 由 (01111) 表示 -1，(10000) 表示 0，(10001) 表示 1 ......
最后，剩下了 (11111) 与 15，配为一对

于是，这个问题似乎就解决了，因为这种映射同样保持了简单的后继运算！

是的，如果计算机确实是只用于处理外部整数的机器，并且所有需要处理的数都在 $[- 16, 15] \cap Z$ 中，那么我想以上随手构造的映射就非常完美，不会出错且计算高效，然而，为什么它不可用于现实中的计算机？理由至少有两点：

无论如何，计算机需要处理各种不同大小的数，特别地，需要处理不同值域的数据，如果采用以上的映射方式，则对于不同的 $k$ ，映射关系完全不同，这意味着如果要在 $k_{1}$ 与 $k_{2}$ 之间进行类型转换会比较困难
熟知，减法作为加法的逆运算而存在，为了计算减法，必须先对减数进行求逆操作，设想对十进制中的 5 求逆，只需要加一个负号成为 -5 即可，这种对称性没有被保持到二进制中，所以重要的求逆操作计算量更大

由此，我们得到了又一个先验假设：映射应当具有稳定性和对称性：

稳定性：类型转换容易
对称性：对加法求逆容易

我们在后继这个一元运算中已经获得了一个重要经验：某个一元运算容易，意味着运算的输入与输出相似或相近，首先，我们希望保持 “0-1” 串的后继运算规则不变，这样就不必重新担心它，其次，要寻找一种新的映射方式满足稳定性和对称性，即：类型转换和求逆前后的 “0-1” 串相似或相近！

事情变得有趣了起来，在第一节，我们先确定了集合 $A$ 上的后继运算，然后按照后继顺序依次为 $A$ 中元素 $a$ 分配 $B$ 中元素 $b$ ，这样就轻松保持了同构，公式是：

f (b * *) = f (b) + + ⟺ f^{- 1} (f (b * *)) = f^{- 1} (f (b) + +) ⟺ b * * = f^{- 1} (f (b) + +)

现在情况则相反了！我们确定 $B$ 上的后继运算不变，00000 的后继一定是 00001，11001 的后继一定是 11010，并期望由以下的公式保持同构（ $c$ 为 $C$ 中元素， $π π$ 为 $C$ 上的后继运算， $b$ 为 $B$ 中元素， $* *$ 仍为 $B$ 上的后继运算， $C$ 到 $A$ 的双射为 $g$ ）：

g (c π π) = g (c) * * ⟺ g^{- 1} (g (c π π)) = g^{- 1} (g (c) * *) ⟺ c π π = g^{- 1} (g (c) * *)

也就是说，我们按照后继顺序依次为 $B$ 中元素 $b$ 分配 $c$ 构成映射，那么我们按照 $c$ 被分配的顺序定义 $C$ 上的后继即可，不可忽视的一点是， $B$ 必然在后继运算 $* *$ 下构成一个环（图论上的而非代数上的），于是我们可以任意选取分配的起点，并且 $C$ 必然也将在后继运算 $π π$ 下构成一个环，于是，整个过程可以理解成，将 $C$ 连接成一个环，然后与 $B$ 以任意方式对齐！

不失一般性，以下设 $k = 4$ ：

先成环再对齐，这个视角首先能够为如何满足稳定性带来一些启发：我们把 $C$ 中的 0 与 $B$ 中的 (00000) 对齐，这样可以保证 $k_{1} = 3$ 和 $k_{2} = 114$ 下的 0 都以全 0 串表示，这必然为类型转换带来很大的方便
现在已经规定了两个环如何对齐，而 $B$ 成环的方式确定，那么可变的只有 $C$ 成环的方式，我们知道，一共有 $(2^{k + 1} - 1)! = 31!$ 种不同的成环方式（圆排列），但其中只有很小一部分是备选项。为了使 $C$ 与 $B$ 的映射本身容易计算，在不考虑边界时，我们仍然希望 0 的后继是 1，1 的后继是 2 而不是 5，至于 -2 的后继是 -1 还是 -3 则留给后续讨论
现在情况缩减到了几种？所有非负数内部连续连接，只有一种方向，所有负数内部连续连接，有两种方向，我们把这两条子链拼接起来，实际上只剩下了两种可能！！
第一种是：

0 \to 1 \to 2 \to \dots \to 15 \to - 1 \to - 2 \to \dots \to - 15 \to - 16 \to 0

第二种是：

0 \to 1 \to 2 \to \dots \to 15 \to - 16 \to - 15 \to \dots \to - 12 \to - 1 \to 0

对于两种情况，分别绘制成环，与环 $C$ 对齐，观察对称性，容易知道第二种才是最优的选择，因为此时所有正数都与负数在环上关于 0 对称！
于是，这一种对应方式就是现今大部分计算机存储有符号整数的方式，也就是补码！！！

3. 补码的定义

恭喜！ 来到本节时，我们已经从零开始，共同重新发明了补码！整个过程都是十分自然的，实际上，稍好的直觉完全可以使你跳过几步，来到终点。因此，补码并非什么天才的创造，而是自然的相反。遗憾的是，很大一部分人，包括我自己，是这样初次接触它的：

非负数的补码是原码本身，负数的补码是原码的非符号位取反再加一

总之，在这一节，我们将把上文推导得到的补码定义与其他定义和性质结合起来。

视起点为环 $C$ 上的 -16，即环 $B$ 上的 (10000)，

- 16 \to - 15 \to - 14 \to \dots \to - 1 \to 0 \to 1 \to \dots \to 14 \to 15 \to - 16

现从 -15 归纳至 -1，证明 “负数的补码是原码的非符号位取反再加一”，记号与第二节相同，另记 $C$ 中元素到原码的映射为 $φ$ ：

g (- 16) = g (15 π π) = g (15) * * = (01111) * * = (10000)

g (- 15) = g (- 16 π π) = g (- 16) * * = (10000) * * = (10001)

$φ (- 15)$ = (11111)，命题成立，而自变量 $c$ 加一时， $φ (c)$ 减一，其取反加一，而 $g (c)$ 加一，故保持相同，证毕.

注意到此时环 $C$ 上的数单调递增，全加上 16 后，就成为了 32 的最小完全剩余系，那么利用模的性质，可以形式地定义 $c π π = ((c + 17) \mod 32) - 16$

关于二进制形式求逆的实际计算方式，可观看 Nand2Tetris-负数