CDN Space
Learn Skills ,Record Life
CDN Space

[转载]补码原理的个人理解

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

同余

钟表的例子

图1:

在这里插入图片描述

将时针从 10 点调到 5 点可以将时针逆时针方向拨 5 格,也可以顺时针方向拨 7 格,于是可以看成 − 5 -5 5 + 7 +7 +7是一样的效果:

  • 时针逆时针方向拨 5 格,相当于做减法: 10 − 5 = 5 {10-5=5} 1055

  • 时针顺时针方向拨 7 格,相当于做加法: 10 + 7 = 17 ≡ 5 ( m o d 12 ) {10+7=17\equiv 5\pmod {12}} 10+7=175(mod12)

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

很容易看出:

5 + 7 = 12
4 + 8 = 12
3 + 9 = 12
... 
  • 1
  • 2
  • 3
  • 4

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

在数学中,用「同余」概念描述上述关系,两个整数 a、b,若它们除以整数 m 所得的余数相等,则称 a 与 b 对于模 m 同余,记作:
a ≡ b ( m o d n ) {a\equiv b\pmod n} ab(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}} 10510+7=17(mod12)
1 − 5 ≡ 1 + 7 = 8 ( m o d 12 ) {1 – 5 \equiv 1 + 7 = 8 \pmod{12}} 151+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 负数的补码,就是用模减去该数字绝对值的原码
  • 1
  • 2
  • 3

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

二进制补码

在计算机中,假设用 4 bit 来存储数,
4 bit 能表示 16 ( 2 4 {2^4} 24)个数,16 是模。模就是 1111 + 1 的结果(10000),已经超出 4 位能表示的范围,10000 就好比除数,取模的结果正好都是小于除数的。我们将这些二进制数都在环上进行表示,首位为 0 表示正数,首位为 1 表示负数:
图2:

图2

4 位有符号整数能表示的最大值也就是上限是 2 3 − 1 {2^3-1} 231,最小值也就是下限是 − 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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

当最大值 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 就好了,
   也不用纠结了。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

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

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

看图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,
溢出就相当于取模,
我们最后得到的结果就是取模的结果。
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

总结

模是 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,2311]

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

参考:
从计算机为什么用补码存储数据,衍生到存储单元数据溢出
Class #7 – Signed Binary Numbers, Subtraction and Overflow
原码、反码和补码
取模运算与取余运算的区别

赞赏
版权声明:本文为CSDN博主「DesireToBeGreat」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/jiaobuchong/article/details/83188674

CDN

文章作者

发表评论

textsms
account_circle
email

CDN Space

[转载]补码原理的个人理解
大学的时候就学了补码,但很长一段时间都没有理解。突然某一天看到 Java 的 byte 的类型表示的范围是 [ − …
扫描二维码继续阅读
2021-03-11