补码原理的个人理解

Myth丶恋晨 2022-05-11 12:04 270阅读 0赞

大学的时候就学了补码，但很长一段时间都没有理解。突然某一天看到 Java 的 byte 的类型表示的范围是 \[ − 128 , 127 \] \[-128, 127\] \[−128,127\]，按照最高位是符号位，一个 byte 能表示的最大正数是 128（ 2 7 − 1 \{2^7 - 1\} 27−1），然后负数是存的补码，最小能表示到 -128，那为什么是 -128 呢？这一下勾起了我的兴趣，我要去彻底弄明白这个东西。搜了一波网上的文章，看了之后反正是晕乎乎的，下面将以我的思路来表述一下我对补码的看法。

### 同余 ###

#### 钟表的例子 ####

图1：  
![在这里插入图片描述][70]  
将时针从 10 点调到 5 点可以将时针逆时针方向拨 5 格，也可以顺时针方向拨 7 格，于是可以看成  − 5 -5 −5 和  \+ 7 +7 \+7是一样的效果：

*  时针逆时针方向拨 5 格，相当于做减法： 10 − 5 ＝ 5 \{10-5＝5\} 10−5＝5
 *  时针顺时针方向拨 7 格，相当于做加法：  10 + 7 = 17 ≡ 5 ( m o d 12 ) \{10+7=17\\equiv 5\\pmod \{12\}\} 10\+7=17≡5(mod12)

这里的前提是有 12 这个数作为上限的，当和超过 12，则将 12 舍去，其实也就是取模。于是类推就有减 4 可表示成加 8，减 3 可表示成加 9……

很容易看出：

5 + 7 = 12
    4 + 8 = 12
    3 + 9 = 12
    ...

这些数对的和都一样，称这些数互补。

在数学中，用「同余」概念描述上述关系，两个整数 a、b，若它们除以整数 m 所得的余数相等，则称 a 与 b 对于模 m 同余，记作：  
 a ≡ b ( m o d n ) \{a\\equiv b\\pmod n\} a≡b(modn)

取模时结果符号与被除数是一致的：  
7 % 12 = -5 % 12 = 7，当 M ＝ 12 时，－5 和 ＋7，－4 和 ＋8，－3 和 ＋9就是同余的。  
综上：  
 10 − 5 ≡ 10 + 7 = 17 ( m o d 12 ) \{10 -5 \\equiv 10 + 7 = 17 \\pmod\{12\}\} 10−5≡10\+7=17(mod12)  
 1 − 5 ≡ 1 + 7 = 8 ( m o d 12 ) \{1 - 5 \\equiv 1 + 7 = 8 \\pmod\{12\}\} 1−5≡1\+7=8(mod12)

在有模这个规则的限定下，到这里是不是感觉可以使用加法来进行减法运算了，基于同余的概念，模是 12，对于「－5 和 ＋7，－4 和 ＋8，－3 和 ＋9」这几组数，假设 7 是 -5 的补码，8 是 -4 的补码，9 是 -3 的补码。  
减法运算就可以转成补码的加法运算：8 - 5 = 8 + 7 （mod 12）。

这里可以得出补码计算方式：

/  X       正数和 0 的补码，就是该数字本身
     [X]补 = |
    　　　　　　\ 模 －|X| 原码    X < 0 负数的补码，就是用模减去该数字绝对值的原码

那计算机是不是可以使用补码去表示负数呢？  
答案是肯定的，计算机将一个负数以补码的方式存储，这样计算机也不用进行减法运算了。在模一定的情况下，取模的结果就是我们想要的值。

### 二进制补码 ###

在计算机中，假设用 4 bit 来存储数，  
4 bit 能表示 16 （ 2 4 \{2^4\} 24）个数，16 是模。模就是 1111 + 1 的结果（10000），已经超出 4 位能表示的范围，10000 就好比除数，取模的结果正好都是小于除数的。我们将这些二进制数都在环上进行表示，首位为 0 表示正数，首位为 1 表示负数：  
图2：  
![图2][2]  
4 位有符号整数能表示的最大值也就是上限是  2 3 − 1 \{2^3-1\} 23−1，最小值也就是下限是 − 2 3 \{-2^3\} −23（1000）。计算机无法表示无穷大和无穷小的数字，无论何种数据类型都有一个上限和下限，超过了限定就会产生溢出。超出了上限就叫上溢出（overflow），超出了下限就叫下溢出（underflow）。从图中可以看出，`0111（最大的数） + 1` 会产生上溢出，然后就会从下限开始，变成了最小的数值，这不就是前面所讲的取模吗。所以计算机数值的溢出，就相当于取模，那我们前面所讲的同余的概念就可以在这个地方使用了。

一个4位的二进制数能表示的数是有限的，从 0000 ~ 1111 ，0000表示0，1111表示 - 1，最大值7（0111），最小值-8（1000）。

来一组计算：

0000 + 0001 = 0 + 1 = 0001 = 1
    0001 + 0001 = 1 + 1 = 0010 = 2
    0010 + 0001 = 2 + 1 = 0011 = 3
    ...
    0111 + 0001 = 7 + 1 = 1000 = -8
    1000 + 0001 = -8 + 1 = 1001 = -7
    1001 + 0001 = -7 + 1 = 1010 = -6
    ...
    1111 + 0001 = -1 + 1 = 0000 = 0
    0000 + 0001 = 0 + 1 = 0001 = 1

当最大值 7 + 1 后，产生上溢出，然后从下限 -8 开始，继续周而复始又变成了0000，就像钟表一样，循环往复。

现在有一个数字 3，让它变成0，怎么办？  
有两种方法:

1.  可以逆时针移动 3 位，也就是：0011 - 0011 = 0000
2.  可以顺时针移动 13 位，也就是：0011 + 1101 = 0000

这里的模是 10000，当一个四位的二进制数 abcd 减去另一个四位二进制数 efgh ： abcd - efgh = abcd + (模 - efgh) ，（模 - efgh）是 -efgb 的补码，我想这也就是补码的由来，或者你可以取一个其他的名字。

补码的计算以及下限 -8 的由来（我比较 trick 的想法）：

1. -0 的补码是「模 - 0 的原码」，也就是 10000 - 0000 = 10000，已经溢出了，还是 0000，-0 用还是用 0 表示就好了
    2. -1 到 -7 的补码计算方式也是一样的
    3. 那 -8（下限） 又是怎么来的呢？
       把这个当成特殊 case 来处理吧，因为 4 bit 无法表示 8，
       正常 -8 的补码计算方式是 10000 - 01000 = 1000，
       在图2 的圆环上有对应的值，那我们就用 1000 表示 -8 就好了，
       也不用纠结了。

很多教材会说负数的补码等于绝对值的原码取反加一，那这个又是怎么来的呢？  
本文中说的补码的求法是：`补码 = 模 - |x|(绝对值原码)`，比如要求 -7 的补码：

10000（模）- 0111 
    = 1111 + 1 - 0111
    = 1111 - 0111 + 1 (加法交换率)   // 1111 - 0111 这一步相当于取反
    = 1000 + 1   // 于是可以得出「补码=绝对值的原码取反 + 1」

看图2 中，在模是  2 4 2^4 24，4 bit 所能表示的数都在环上标出，x 和 y 是环上的点，  
所有的 `x -y` 都转换成 `x + (-y)`，`-y` 用补码表示，直接将 x 的二进制和 `-y` 的补码二进制相加即可得到 `x-y` 的结果。

通过负数的补码将减法转换为加法，出现的进位就是模，舍去即可。

4 - 2 = 2 
      0100
    + 1110
    ----------
     10010
    这里出现了进位，舍去进位。
    结果 10010 超过模了，其实舍去就相当于 10010 - 10000（类似mod M）= 0010，
    溢出就相当于取模，
    我们最后得到的结果就是取模的结果。

### 总结 ###

模是 m，在模的基础上，-a 和 m - a 对于模 m 同余，m-a 是 -a 的补码。于是计算机中用 m-a 表示 -a，x - a = x + m - a (模是 m ），溢出就相当于是在取模。所以这也是我理解为什么使用补码的原因，其实就是数学里「同余」的概念，你会发现我们操作的其实就是在进行取模运算，这是一个很精妙的算法，它规避了在计算机中进行减法器的运算。

### 最后 ###

4 位二进制数的模是  2 4 = 16 \{2^4\}=16 24=16，  
8 位二进制数的模是  2 8 = 256 \{2^8\}=256 28=256，  
16 位二进制数的模是  2 16 = 65536 \{2^\{16\}\}=65536 216=65536，  
32 位二进制数的模是  2 32 \{2^\{32\}\} 232，

4 位二进制补码最多能表示  2 4 \{2^\{4\}\} 24（16 个数），数的范围是  \[ − 8 , 7 \] \[-8, 7\] \[−8,7\],  
8 位二进制补码最多能表示  2 8 \{2^\{8\}\} 28（256 个数），数的范围是  \[ − 128 , 127 \] \[-128, 127\] \[−128,127\],  
16 位二进制补码最多能表示  2 16 \{2^\{16\}\} 216（65536 个数），数的范围是  \[ − 32768 , 32767 \] \[-32768, 32767\] \[−32768,32767\],  
32 位二进制补码最多能表示  2 32 \{2^\{32\}\} 232 个数，数的范围是  \[ − 2 31 , 2 31 − 1 \] \[\{-2^\{31\}, \{2^\{31\} - 1\}\}\] \[−231,231−1\]。

这篇文章讲得挺好的，看完之后对补码的理解变得有些清晰了：[补码(为什么按位取反再加一)：告诉你一个其实很简单的问题][Link 1]

参考：  
[从计算机为什么用补码存储数据，衍生到存储单元数据溢出][Link 2]  
[Class \#7 - Signed Binary Numbers, Subtraction and Overflow][Class _7 - Signed Binary Numbers_ Subtraction and Overflow]  
[原码、反码和补码][Link 3]  
[取模运算与取余运算的区别][Link 4]

[70]: /images/20220505/42388abd6cce4d059fb37399a60b97e5.png
[2]: /images/20220505/3bbaafd1b7b6496db54584c88b9c3de1.png
[Link 1]: https://blog.csdn.net/wenxinwukui234/article/details/42119265
[Link 2]: https://www.jianshu.com/p/63cc96758d20
[Class _7 - Signed Binary Numbers_ Subtraction and Overflow]: http://users.dickinson.edu/~braught/courses/cs251f02/classes/notes07.html
[Link 3]: https://www.douban.com/note/223507364/
[Link 4]: https://baike.baidu.com/item/%E5%8F%96%E6%A8%A1%E8%BF%90%E7%AE%97/10739384?fr=aladdin