手把手教你发明补码#

溢出带来了循环群🔥#

受限于存储位数 $n$ 的限制，机器对无符号整数的加法并不封闭．

4 位二进制加法溢出现象

$$(1011)_2 + (0111)_2 = (0010)_2$$

也就是

$$11 + 7 = 2$$

溢出这种特点，决定了机器对无符号整数的加法是一种模 $2^n$ 加法．而我们又知道模 $2^n$ 加法群 $G = \langle \mathbb Z_{2^n}, + \rangle$ 是一种 $2^n$ 阶循环群，因此群内所有数都存在相应的逆元．

我们知道整数的减法是利用普通加法群下的逆元实现的，那能否利用 $G$ 内所有数存在逆元这一特点，来设计一种编码：让非负整数编码不变，让负整数编码成在 $G$ 下相应绝对值的逆元，以此构建机器加法和整数加法的局部同构，实现机器对一定范围内普通整数的减法功能？

恭喜你，你发明了补码．

你发明的补码#

以 4 位二进制补码为例，你最初的设计方案是

尴尬的事情发生了：你发现机器数还剩下 $8$ 没用上，你又不想浪费这个数．

这个机器数 $8$ 应该被译码成真值 $8$ 还是 $-8$ 呢？感觉好像直接译成真值 $8$ 省事诶…

我看未必🤗，你设计的时候是省事了，但对于机器来说，某些情况下却不省事：

🤖：从真值 $-1(1111)$ 到真值 $-7(1001)$，编码出的机器数最高位都是 $1$，想必最高位是 $1$ 的机器数译出来的一定是负数吧！😝

🤖：我趣，这个机器数 $1000$ 怎么译出来的是正整数 $8$？😵

可见我们把机器数 $8$ 译成真值 $-8$ 更有利于机器判断真值的正负．