浅谈补码的原理和正确性
前言
upd 2022.2.14 我就该早点看《计算机组成原理》，补码的定义就是
一个 $n$ 位二进制数 $N$ 的二进制补码定义为 $2^n-N$
不过本文还是严谨证明了它的正确性，以下为原文
补码是怎么来的？
负数的补码为什么是按位取反（除了符号位）再加 $1$ ?
补码的正确性能保证吗？
补码背后的数学原理是什么？
本文围绕原理和正确性介绍了补码
一、我们为什么用补码？
我们以 $8$ 位二进制数为例
$8$ 位无符号数，可以表示 $0\sim255$ 以内的数（即 $00000000 \sim 11111111$ ），那么如果我们要表示负数呢？
我们都知道正、负号能够表示正、负数，可是计算机“看不懂“，它只能识别 $0,1$
于是，就出现了原码
最高位表示数的正负，$0$ 表示 正 ，$1$ 表示负
$8$ 位有符号数，以原码形式存储则可以表示 $0 \sim 127$（即 $00000000 \sim 01111111$ ） 和 $-127 \sim 0$ （即 $11111111 \sim 10000000$ ）
相信看到这里，你应该发现了：以原码形式存储时，$0$ 的值不唯一
我们把 $\pm 0$ 的问题放一边，先来讨论一下编码的正确性
计算 $1+(-1)$
$00000001 + 10000001 = 10000010$
然而 $10000010$ 转成十进制是 $-2$ ！
由此可知原码不可以直接进行运算，或者可以认为以原码的编码方式运算是错误的
那么问题来了，正数的表示都符合我们的习惯，那么问题一定出在负数上
二、补码是怎么来的？
各大教科书上都会告诉你，正数的补码就是它的原码，负数的补码就是原码按位取反（除了符号位）再加 $1$
你是不是也很迷惑？补码到底为什么是这么算出来的？
我们还是以 $8$ 位有符号数为例
我们知道，两个数如果互为相反数则和为$0$ ，例如 $1+(-1)=0$
那么正确的编码方式中 $1+(-1)$ 一定等于 $0$
我们设 $-1$ 的编码为 $\phi$ ，可得 $00000001 + \phi = 0$
$\therefore \phi = 11111111$（注：计算过程将在下文中讲述，这里只需要知道结果）
那么就很清楚了，如果我们已知编码 $\phi$ ，它的相反数的编码就是 $0 - \phi$
现在我们来讨论一下 $\pm 0$ 的问题，显而易见，$10000000$ 肯定是不符合常理的（ $00000000 + 10000000 \ne 00000000$ ）
那么 $10000000$ 对应的相反数的编码是什么呢？
设 $10000000 + \phi = 0$ 解得 $\phi = 100000000$ （注意位数！）
我们会发现 $00000000 \sim 11111111$ 已经无法表示了
那 $0$ 呢？$0$ 的相反数还是 $0$ ，就是它本身
事已至此，干脆就让它们单身着吧。 既然 $10000000$ 的第一位是 $1$ ，表示负数，那就规定它为负数，因此 $10000000$ 就代替了 $-128$
因为 $10000000$ 没有对应的相反数的编码，所以没有 $+128$
然后每个数都有了自己对应的编码，$1 \sim 127$ 对应 $-1 \sim -127$ ，加上两个单身汉 $0$ 和 $-128$
这种编码就叫补码
那么为什么负数的补码是原码按位取反再加 $1$ 呢？
我们再看 $1+(-1)=0$ 的例子
设 $00000001 + \phi = 00000000$
$\therefore \phi = 00000000-00000001$
一个小的数减一个大的数，怎么办？
首先我们应该都知道溢出这一概念
那么 $00000000$ 就可以看作 $11111111 + 00000001$
$\therefore\ \phi = (11111111 + 00000001) - 00000001$
$\qquad= (11111111-00000001) + 00000001$
注：这个就是简单的结合律
我们看前面一部分，不就是按位取反嘛（反码）！
相信你现在应该理解了，如果我们要求正数 $\lambda$ 的相反数 $\mu$ 的补码
$\mu = (11111111-\lambda) + 00000001$ ，
即 $\lambda$）按位取反（包括符号位）再加 $1$ ，当然也是 $\mu$ 按位取反（除了符号位）再加 $1$ ，一样的
三、补码的正确性能保证吗？
1.符号位能保证本身的值、运算结果的值正确吗？
本身的值肯定正确，运算结果的值也正确
运算都是从最低位运算到最高位，这个符号位又加在最高位，不可能影响运算，只可能被影响（注：接下来我们就来证明这个影响不会对运算结果的符号正确性产生影响）
2.数学运算结果的符号能保证正确吗？
为了方便理解和证明，我们以 $4$ 位有符号数为例（即 $-8 \sim 7$ ）
注意：正确性指在数学运算结果不溢出的情况下位运算的结果和数学运算的结果正确
首先，易知任何合法的数与 $0$ 作运算结果一定正确
1) 值的位运算结果不溢出时
1.正数+正数
数学运算结果：一定为正数，符号为正
位运算结果：值的位运算不溢出，符号位 $0+0=0$，仍为正
设这里两个数补码分别为$[0a_2a_1a_0], [0b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $A+B$
且 $0 < A+B \le 7$
值的位运算结果不溢出即 $-8 \le A+B \le 7$
$\{x|0 < x \le 7\}\subsetneqq\{x|-8 \le x \le 7\}$
故该情况$\color{red}{正确}$
2.负数+负数
数学运算结果：一定为负数，符号为负
位运算结果：值的位运算不溢出，符号位 $1+1=0$ ，变成了正
设这里两个数补码分别为$[1a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $-8+A+（-8）+B = -16+A+B$
且 $-8 \le A+B-16 < 0 \Rightarrow 8 \le A+B < 16$
值的位运算结果不溢出即 $-8 \le A+B \le 7$
$\{x|-8 \le x \le 7\}\cap\{x|8 \le x < 16\} = \varnothing$
故该情况$\color{red}{不存在}$
3.一正一负
a.正数绝对值大于负数绝对值
数学运算结果：一定为正数，符号为正
位运算结果：值的位运算结果不溢出，符号位 $0+1=1$ ，变成了负
设这里两个数补码分别为$[0a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为$A+(-8)+B = A+B-8$
且 $0 < A+B-8 \le 7 \Rightarrow 8 < A+B \le 15$
值的位运算的结果不溢出即 $-8 \le A+B \le 7$
$\{x|-8 \le x \le 7\}\cap\{x|8 < x \le 15\} = \varnothing$
故该情况$\color{red}{不存在}$
b.正数绝对值等于负数绝对值
数学运算结果：$0$ ，符号为正
位运算结果：值的位运算结果不溢出，符号位 $0+1=1$ ，变成了负
设这里两个数补码分别为$[0a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为$A+(-8)+B = A+B-8 = 0 \Rightarrow A+B=8$
值的位运算的结果不溢出即 $-8 \le A+B \le 7$
$\{x|-8 \le x \le 7\}\cap\{x|x=8\} = \varnothing$
故该情况$\color{red}{不存在}$
c.正数绝对值小于负数绝对值
数学运算结果：一定为负数，符号为负
位运算结果：值的位运算结果不溢出，符号为 $0 + 1 = 1$ ，仍为负
设这里两个数补码分别为$[0a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $A+(-8)+B = A+B-8$
且 $-8 \le A+B-8 < 0 \Rightarrow 0 \le A+B < 8$
值的位运算结果不溢出即 $-8 \le A+B \le 7$
$\{x|0 \le x < 8\}\subsetneqq\{x|-8 \le x \le 7\}$
故该情况$\color{red}{正确}$
2) 值的位运算结果溢出时
1.正数+正数
数学运算结果：一定为正数，符号为正
位运算结果：值的位运算结果溢出，符号位 $0+0+1=1$ ，变成了负
设这里两个数补码分别为$[0a_2a_1a_0], [0b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $A+B$
且 $0 < A+B \le 7$
值的位运算结果溢出即 $A+B>7$
$\{x|0 < x \le 7\}\cap\{x|x>7\} = \varnothing$
故该情况$\color{red}{不存在}$
2.负数+负数
数学运算结果：一定为负数，符号为负
位运算结果：值的位运算结果溢出，符号位 $1+1+1=1$ ，仍为负
设这里两个数补码分别为$[1a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $-8+A+(-8)+B = A+B-16$
且 $-8 \le A+B -16< 0 \Rightarrow 8 \le A+B < 16$
值的位运算结果溢出即 $A+B>7$
$\{x|8\le x < 16\}\subsetneqq\{x|x>7\}$
故该情况$\color{red}{正确}$
3.一正一负
a.正数绝对值大于负数绝对值
数学运算结果：一定为正数，符号为正
位运算结果：值的位运算结果溢出，符号位 $0+1+1=0$ ，仍为正
设这里两个数补码分别为$[0a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $A+(-8)+B = A+B-8$
且 $0<A+B-8\le 7 \Rightarrow 8<A+B\le15$
值的位运算结果溢出即 $A+B>7$
$\{x|8< x \le 15\}\subsetneqq\{x|x>7\}$
故该情况$\color{red}{正确}$
b.正数绝对值等于负数绝对值
数学运算结果：$0$ ，符号为正
位运算结果：值的位运算结果溢出，符号位 $0+1+1=0$ ，仍为正
设这里两个数补码分别为$[0a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $A+(-8)+B = A+B-8 = 0 \Rightarrow A+B=8$
值的位运算结果溢出即$A+B>7$
$\{x|x=8\}\subsetneqq\{x|x>7\}$
故该情况$\color{red}{正确}$
c.正数绝对值小于负数绝对值
数学运算结果：一定为负数 ，符号为负
位运算结果：值的位运算结果溢出，符号位 $0+1+1=0$ ，变成了正
设这里两个数补码分别为$[0a_2a_1a_0], [1b_2b_1b_0]$
令 $A = \sum\limits_{i=0}^{2}{a_i\times 2^i}, B = \sum\limits_{i=0}^{2}{b_i \times 2^i}$，易知 $A,B \in \N$
原式可化为 $A+(-8)+B = A+B-8$
且 $-8\le A+B - 8<0 \Rightarrow 0 \le A+B <8$
值的位运算结果溢出即 $A+B>7$
$\{x|0 < x < 8\}\cap\{x|x>7\} = \varnothing$
故该情况$\color{red}{不存在}$
综上所述，所有存在的情况中，符号都是正确的，因此补码的正确性是可以保证的
总结
本文简单解释了补码的原理
并证明了补码的正确性
参考文献
[1] 《补码正确性的证明》
