# 计算机二进制补码 大学的老师告诉我们: "正数的原码、反码、补码是一样的, 负数的补码是原码除符号位外，其余各位取反再加1。" 但是实际上，**补码仅仅是一种编码，好处是可以用加法来实现减法的操作，和原码、反码没啥太大的关系**，口诀只是为了人类计算方便 ## 二进制 在十进制中，可以用 $0\sim9$ 来表示有一数，16 记为 16，权重为 $10^n$ `16` 表示  $1 * 10^1 + 6 * 10^0 = 16$ 在16进制中，可以用$0\sim F$ 来表示一个数，16 记为 0x10，权重为 $16^n$ `0x10` 表示 $1 * 16^1 + 0 * 16^0 = 16_{[10]}$ 在二进制中，只能用  $0, 1$ 来表示一个数，那么 16 就记为`10000` ， 权重是 $2^n$ `10000` 表示 $1 *2^4 + 0 * 2^3 + 0 *2^2 + 0 * 2^1 + 0 * 2^0 = 16_{[10]}$ 于是我们就有了一个新的计数方法，二进制: | 十进制 | 二进制 | | --- | --- | | 0 | 000 | | 1 | 001 | | 2 | 010 | | 3 | 011 | | 4 | 100 | | 5 | 101 | | 6 | 110 | | 7 | 111 | ## 加法 但是光有计数还不够，我们还需要有计算，二进制中封二进一，假如我们自己实现了一个全加器： $010_{[2]} + 100_{[2]} = 110_{[2]} = 6_{[10]}$ $011_{[2]} + 001_{[2]} = 100_{[2]} = 4_{[10]}$ ## 减法 有了加法器，那还得有一个减法器，假如我们又自己实现了减法器（**现代计算机没有减法器，暂时先忘掉这个，后面我会讲怎么用加法实现减法**）： $001_{[2]} - 101_{[2]} = -100_{[2]} = -4_{[10]}$ 没啥问题，但是出现了一个负数。可以计算机中只有 1 和 0 ，没有我们日常使用的 `+,-`号，怎么去表示负数 ## 负数 正如我们数学中约定的 `+`和 `-`来表示一个数的正负一样，于是我们决定使用其中的一个符号来表示符号的 `+` 和 `-` ，那就用最高位来表示吧。**0 表示正，1 表示负** | 十进制 | 二进制【使用正负号】 | 二进制【使用0、1代表正负号】 | | --- | --- | --- | | +0 | +00 | 000 | | +1 | +01 | 001 | | +2 | +10 | 010 | | +3 | +11 | 011 | | -0 | - 00 | 100 | | -1 | - 01 | 101 | | -2 | - 10 | 110 | | -3 | - 11 | 111 | 现在我们的可计数示范围由 $0 \sim 7$ 变成了 $-3 \sim +3$ **注意：区别与网上其他说法，最高位是符号位，表示的是正和负没错，但是我们现在有减法器，计算的时候符号位可以特殊处理，也请先忘掉加法实现减法的结论** 假如计算机有`+,-`号，先我们的减法器验证一下： $$\begin{aligned} & 1-3 \\ & = (+01) - (+11) \\ & =(+01_{[2]}) - (+11_{[2]}) \\ & = -|11_{[2]}-01_{[2]}| \\ & = -10_{[2]} \\ & = -2_{[10]} \\ \end{aligned}$$ 此时用我们约定的符号来替换正负号， **负号换成 1 ，正号换成 0** $$\begin{aligned} & (001_{[2]}) - (011_{[2]}) \\ & = -|11_{[2]}-01_{[2]}| \\ & = -10_{[2]} = 110_{[2]} \\ & = -2_{[10]} \end{aligned}$$ 我们知道 $X - Y = X + (-Y)$， 所以上面的运算等价 ： $$\begin{aligned} & (001_{[2]}) - (011_{[2]}) \\ & = 001_{[2]} + 111_{[2]} \\ & = -|11_{[2]} - 01_{[2]}| \\ & = 110_{[2]} \\ & = -2_{[10]} \\ \end{aligned}$$ > **注意我们有减法器，这里我们的最高位此时是符号位，符号会被提出来，并不会参与运算** > > **再次注意：区别与网上其他说法，最高位是符号位，表示的是正和负，我们现在有减法器，计算的时候符号位可以特殊处理，也请先忘掉加法实现减法的结论** > > 比如我们十进制计算 1 - 3 = 1 + (-3)， 当一个较小数减去一个较大数的时候， 我们一般步骤是用大数减去小数取**绝对值**，然后结果取其**相反数** > > 例如我们平时计算 1- 3 = 1 + (-3): > > $$\begin{aligned} & 1 - 3 \\ & = 1 + (-3) \\ & = - | 3 -1 | \\ & = - |2| \\ & = -2 \end{aligned}$$ > > 那么二进制减法器也一样的，最高位的符号位也是特殊处理，提出来再计算的： > > $$\begin{aligned} & 001 - 011 \\ & = 001 + (111) \\ & = - |11 - 01| \\ & = - |10| \\ & = -10 \\ & = 110 \\ \end{aligned}$$ 上面这种编码方式我们取一个名字，就叫 **原码**。 加法和减法以及符号都搞定了，不过我们需要实现一个减法器才能计算，而且处理符号也比较麻烦，**有没有可能用加法实现减法**，当然可以！ ## 模和同余 > 数论中的重要概念。给定一个正整数，如果两个整数a和b，满足 $a-b$ 能够被 $m$ 整除，即 $\frac{a - b}{m}$ 得到一个整数， > > 那么就称整数a与b对模m同余，记作 $a \equiv b (mod\;m)$。 > > 对模m同余是整数的一个**等价**关系。 “模”是指一个计量系统的计数范围，超出这个范围后就会产生**溢出**，溢出的部分会被直接舍去。例如时钟的计量范围是0-11（1-12），模=12 例如图中这样一个线段围成的圆，计数范围是 0 ~ 7 ，模 m = 8。 ![](https://img-blog.csdnimg.cn/img_convert/4d0394358a2c2306285aec39ad982006.png#crop=0&crop=0&crop=1&crop=1&id=MjVxW&originHeight=331&originWidth=371&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 假如我们现在所处的位置在 1 的位置上，我们要走到 0 这个位置，我们有两种方式 - 退 1 步 - 前进 7 步 (因为模是8，只能表示到 0 ~ 7 ，8 就是 0 ，产生溢出，一个新的轮回开始了) $1 - 1 = 1 + 7 = 0 \Rightarrow -1 \equiv +7 (mod 8)$ 称为+7 是 -1 以 8 为模的补数 也就是说在模为 8 的时候，+7 和 -1 是等价的 同理，假如我们所处 2 的位置上，我们要走到 0 这个位置，也有两种方式： - 退 2 步 - 前进 6 步 $2-2 = 2 + 6 = 0 \Rightarrow -2 \equiv +6 (mod 8)$ 称为+6 是 -2 以 8 为模的补数 也就是说在模为 8 的时候，+6 和 -2 是等价的 由此可见在**模确定的情况下，减去一个数可以由加上一个正数替代，所以一个负数可以用一个正数来表示** ## 补数 > 我们知道在十进制中，如果两个数字的和为 $10^n$ ，那么我们称这两个数互为补数。 > > 例如 1 + 9 = 10 , 2 + 8 = 10, 3 + 7 = 10,  54 + 46 = 100 > > 称 9 是 1 的补数， 8 是  2 的补数, 54 是 46 的补数 那么对应到二进制中，也是一样的，**如果两个数的和为 **$2^n$** ，我们称这两个数互为补数，叫做 2 的补数(2's-compelment)** ![](https://img-blog.csdnimg.cn/img_convert/633acd2d07089ff3ab95bf9058363189.png#crop=0&crop=0&crop=1&crop=1&id=Xifwy&originHeight=371&originWidth=371&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 还是以这个图为例子，由上可知我们模为8，如果我们处于 $011_{[2]}$ 的位置，想要到 $000_{[2]}$ 的位置有两种方式 - 退 3 步 - 进 5 步 十进制： $$\begin{aligned} & 3_{[10]} - 3_{[10]} \\ & = 3_{[10]} + 5_{[10]} \\ & = 0_{[10]} \\ & \Rightarrow - 3_{[2]} \equiv + 5_{[2]} (mod 8) \\ \end{aligned}$$ 二进制： $$\begin{aligned} & 011_{[2]} - 011_{[2]} \\ & = 011_{[2]} + 101_{[2]} \\ & = 000_{[2]} \\ & \Rightarrow - 011_{[2]} \equiv + 101_{[2]} (mod 8) \end{aligned}$$ 我们说，$+ 101_{[2]}$** 是  **$- 011_{[2]}$** 以 8 为模的补数** 于是我们得出一个结论： - **一个负数可用其正补数来代替，而这个正补数可以用模加上负数本身来得到。** - **一个正数和一个负数互为补数时，两数的绝对值之和为模** 由上面的推导我们知道: $-1 \equiv +7 (mod 8)$ $-2 \equiv +6 (mod 8)$ $-3 \equiv + 5 (mod 8)$ $-4 \equiv +4 (mod 8)$ 0 具有特殊性，如果我们处于0 的位置，想要到0 的位置有两种方式： - 退 0 步，进 0 步。也就是不动 - 进 8 步 $-0 \equiv +8 (mod 8)\Leftrightarrow 0 \equiv 0 (mod 8)$ 当然在 模为 8 的计数范围内，我们也没法表示 8 这个数字，8 等于 0，于是就有： $-0 \equiv +8 (mod 8)\Leftrightarrow +0 \equiv +8 (mod 8)\Leftrightarrow -0 \equiv +0 (mod 8)$ 既然 +0 和 -0 等价，就都用0来表示了，消除了 +0 和 -0 的歧义，完善一下我们的图： ![](https://img-blog.csdnimg.cn/img_convert/526e4c5ed84082afada13ba3abd62a4f.png#crop=0&crop=0&crop=1&crop=1&id=fwkiU&originHeight=371&originWidth=371&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 根据上面的结论和推导我们又得出一张表： | 十进制【原码】 | 二进制【补】 | 十进制【补】 | 二进制【原码】 | | --- | --- | --- | --- | | +0 | 000 | 0 | 000 | | +1 | 001 | 1 | 001 | | +2 | 010 | 2 | 010 | | +3 | 011 | 3 | 011 | | -4 | 100 | 4 | | | -3 | 101 | 5 | 111 | | -2 | 110 | 6 | 110 | | -1 | 111 | 7 | 101 | > 关于 4 到底是 + 4 还是 -4 ，其实从补数角度来说都可以，不影响计算结果。 但是我们**人为约定，二进制最高位表示符号，为了统一，所以 4 表示 - 4** > > 而且这个和权重有关系后面会讲到 **现在我们的可计数范围变成了**$-4\sim+3$**，即 **$-2^n \sim 2^n -1(n = 3)$ 看起来不错，这样貌似我们就能实现用加法来计算减法了，验证一下 还是以下面的式子为例： $1 - 3 = 1 + (-3)$ $001_{[2补]} + 101_{[2补]} = 110_{[2补]} = 6_{[10补]} \equiv -2_{[10原]}(mod 8)$ 此时可以发现，用加法实现减法的操作，而且我们没有约定什么最高位为符号位，只是用一个正数来表示一个对应的负数而已，比如：5 表示 -3，6 表示 -2 **我们需要注意，用补数计算的结果也是补数** 上面的这种编码方式取个名字吧，补数补数，干脆就叫做 **补码** ## 关于反码 反码这个东西就是反计算机的，人类为了计算过程不反人类搞了这么一个中间产物，因为在人类计算原码到补码的过程中，发现的一个神奇的现象： - **一个负数的补码正好是其绝对值的原码各位取反再加一** - **一个正数的补码正好就是其本身** 比如 - 3 的补码是 101 ，计算过程是用模减去-3的**绝对值**，或者用模， **mod - |-3|**，我们例子中的模是 8 （即二进制的： 1000），所以 - 3 的补码：8 - 3 = 5 $1000_{[原]} - |111_{[原]}| = 1000_{[原]} - 011_{[原]} = 101_{[补]}$ `1000 - 011` 而我们最多只能表示 3 位，无法表示`1000` ，所以用 `111 + 1` 表示，则 $1000_{[原]} - |111_{[原]}| = 111_{[原]} - 011_{[原]} + 1_{[原]}$ 计算过程就是所谓的负数的补码等于其原码除符号位不变，其余各位取反 + 1 ，**而各位取反的结果就叫做反码(1's compelment)**。所以都是碰巧而已，对应到其他进制的补码可就不是取反+1了，后面会讲到。 ## 关于补码 **补码其实就是一种编码方式，好处在于可以使用加法来实现减法的操作**，和原码、反码没啥太大的关系，**仅仅就是一种编码**，硬要说有啥关系，那就是我们人类计算过程需要**用原码和补码来方便我们人类的计算和识别**。其实计算方式还有另外一种计算补码的方式 因为我们约定了最高位表示符号，那么我们就相当于给其赋予了**负权重** 例如: $111_{[2]} = -1 * 2^2 + 1 * 2^1 + 1 * 2^0 = -4 + 2 + 1 = -1$ $110_{[2]} = -1 * 2^2 + 1 * 2^1 + 0 * 2^0 = -4 + 2 + 0 = -2$ $101_{[2]} = -1 * 2^2 + 0 * 2^1 + 1 * 2^0 = -4 + 0 + 1 = -3$ $100_{[2]} = -1 * 2^2 + 0 * 2^1 + 0 * 2^0 = -4 + 0 + 0 = -4$ $010_{[2]} = -0 * 2^2 + 1 * 2^1 + 1 * 2^0 = -0 + 2 + 0 = 2$ $011_{[2]} = -0 * 2^2 + 1 * 2^1 + 1 * 2^0 = -0 + 2 + 1 = 3$ ## 扩展一下10进制补码 二进制中，我们可以推导出： $2^n -X = Y \Rightarrow -X \equiv Y (mod \; 2^n)$ 称为 2's-compelment。其实扩展到任意数字N，关于其$N^w$的补数  一样适用，可以叫做 N's-compelment， 即： $N^w -X = Y \Rightarrow -X \equiv Y (mod \; N^w)$ 现在假如我们的世界陷入了只能计算**1位数加法**的混沌之中，1 + 9 = 10 ，2 + 8 = 10 这种，会产生溢出等于 0 。 而 4+7 = 11 这种，会产生溢出等于1。 现在我们只能使用$0\sim9$这几个数字了，且失去了正号和负号。（对应计算机的二进制世界，只有0和1，没有正负符号，而且会产生溢出）。 那么我们如何表示负数以及计算减法呢 在这个世界中，我们知道以下规则： - 模是 10 - 一个负数可以由一个正数来表示(模确定的情况下，其的正补数) - 减去一个正数等于加上这个数的相反数（负数） 由于没有了负号，于是聪明的我们决定将$0\sim9$十个数字分成两组，一半表示正，一半表示负。 **不过这样我们能表示的范围就变小了**，变成了 **$-5\sim4$，超过这个范围的数我们没法再表示 规则1：模是 10 规则2：一个负数可以由一个正数来表示 由： $10^1 -X = Y \Rightarrow -X \equiv Y (mod \; 10^1)$ 那么我们可以知道 ： $10 - 1 = 9 \equiv-1(mod\;10)$ $10 - 2 = 8 \equiv-2(mod\;10)$ $10 - 3 = 7 \equiv-3(mod\;10)$ $10 - 4 = 6 \equiv-4(mod\;10)$ $10 - 5 = 5 \equiv-5(mod\;10)$ > 5 表示+5 还是 -5， 完全是我们人为约定的，就像前面二进制中 100 表示 - 4 一样，那只是个计数的符号而已 我们称这种新的计数方称之为 **10 的补数(10's-compelment)**，或者直接叫做**补码**，于是我们可以得出一张对应的关系表： | 十进制补码 | 十进制原码 | | --- | --- | | 0 | 0 | | 1 | 1 | | 2 | 2 | | 3 | 3 | | 4 | 4 | | 5 | -5 | | 6 | -4 | | 7 | -3 | | 8 | -2 | | 9 | -1 | 我们可以用补码来实现计算如下式子 ： $3 - 4 = 3 +(-4)$: 3 的补码是 3， -4 的补码是 6。 $3_{[原]} + (- 4_{[原]}) = 3_{[补]} + 6_{[补]} = 9_{[补]} = -1_{[原]}$ 补码，原来如此！