一篇彻底学懂补码

一篇彻底学懂补码简述补码是计算机运算中的一种数据表示方式,它的存在意义是简化减法的运算。许多人接触补码,仅是被告知是“正数不变,负数取反加一”,而对于为什么需要这么做,以及补码本身的存在意义并不清楚。而网上关于补码的解释比较散,某些网站甚至充斥着太多乱而杂的说法,对初学者(我)而言痛苦不堪,故在此写一篇文章记录,希望其他人少走弯路这篇文章的目的,则是从补码被发明的缘由说起,从根源上:彻底梳理补码形成的过程,说明补码需要解决的问题归纳补码的实质解释补码用于数学运算的正确性解释求补码(负数除符号位以外,按位取

简述

补码是计算机运算中的一种数据表示方式,它的存在意义是简化减法的运算。

许多人接触补码,仅是被告知是“正数不变,负数取反加一”,而对于为什么需要这么做,以及补码本身的存在意义并不清楚。
而网上关于补码的解释比较散,某些网站甚至充斥着太多乱而杂的说法,对初学者(我)而言痛苦不堪,故在此写一篇文章记录,希望其他人少走弯路

这篇文章的目的,则是从补码被发明的缘由说起,从根源上:

  • 彻底梳理补码形成的过程,说明补码需要解决的问题
  • 归纳补码的实质
  • 解释补码用于数学运算的正确性
  • 解释求补码(负数除符号位以外,按位取反加一)这一操作的可靠性
  • 推导补码加减法的运算公式

摈弃错误观念

如果你对补码有以下误解,请从现在起忘记这些错误观点的存在:

  • 补码是让正数变负数,负数变正数
  • 补码是原码数与模互补的数

除了上面的错误观点以外,下面还有几点需要提醒,以免先入为主:

  • 不要把补码与“对模求补”的操作直接关联,只需要把补码看成一种全新构造的二进制编码,不需要过度关注补字
  • 补码的最高位是符号位,但它不是无依据地定义的,后面会解释补码最高位可以代表正负的原因

补码的形成

契机

在计算机的硬件结构中,实现加法器比实现减法器简单的多。人们希望的是构造出一套 “用加法代替减法” 的运算逻辑,构造的结果也就是现在我们所使用的“补码”。

最初的探索

缘起于日常生活的现象,时钟的顺拨与倒拨均可以达到同一钟点
在这里插入图片描述

如上图,十二小时制中,分针由8点拨到6点,有两种方式:

  1. :逆时针拨2小时:8-2=6时
  2. 顺时针拨10小时:8+10=6时

第二种方式本来应该为18时,但由于时钟是十二小时制计时,产生了溢出,显示的是18-12=6时
而第二种形式,则是用加法代替了第一种形式的减法

这正是我们想要的,于是对于“以加代减”的逻辑,有了最初的构造:

时钟超出显示上限,则只显示余下的钟点,这恰好是模数加法运算的体现:
说人话就是:在模12的情况下(或者说对12取余),以下式子是等价的:

( 8 − 2 ) m o d 12 = ( 8 + 10 ) m o d 12 = 6 (8-2)mod12=(8+10)mod12=6 (82)mod12=(8+10)mod12=6

按照这个思路,我们在模范围内,也许可以将“X-Y”的减法变更为“X+Y的补数”的加法。

注:所谓m的补数就是:(模-m)的值,如2的补数是12-2=10

模数加法的局限

模数加法代替减法是一个很好的思路,但它并不是完美的

上面提及到的情况,事实上只是 “大减小” 的情况,如果出现 “小减大” 情况就出现矛盾了:
举个例子,在模100的情况下,套用上面的模数加法公式企图代替减法:

  1. ( 10 − 30 ) m o d 100 = − 20 (10-30)mod100=-20 (1030)mod100=20
  2. ( 10 + ( 100 − 30 ) ) m o d 100 = 80 (10+(100-30))mod100=80 (10+(10030))mod100=80

这和说好的不一样啊,80显然不等于-20,而且也没有因为超越模数而引起取余运算。
然而先贤们并不打算前功尽弃……

负数的表示法

他们为了继续使用模数加法代替减法,他们做了一个大胆而又粗暴的定义:让80等于-20,即用80代表-20

根据这个规律,推广到一般的情况就是:
负数的表示方式就是它绝对值的补数——规则①

这样做有两个好处:

  1. 消除了“小减大”情况下的歧义,使得该情况也可用模数加法代替减法
  2. 此定义同样可以解释“大减小”的情况,因为它同样吻合 将“X-Y”的减法变更为“X+Y的补数” 的说法(视 -Y 作负数,则它的表示为Y的补数

这样做后,无论是“大减小”或是“小减大”,模数加法代替减法都已可适用,可以说已经形成了一套较为通用的以加代减体系。

该负数表示法的结果与缺点

但是注意到,像80这样的大数,失去了自己的意义,在模100的情况下,无法再表示80了。
更一般地,因为我们希望正负数尽量成对出现,而且打算用正数表示负数,这意味着在模100的非负数之间,需要划分一半正数用于表示负数
结合规则①的负数表示方式,最终满足这一系列条件的结果是:

在模100条件下:0 ~ 49表示正数本身; 50 ~ 99表示各自补数的负值(如98代表-2)

更一般地:模n情况下,0 ~ n/2 -1表示本身,n/2 ~ n-1表示各自补数的负值——规则②

补码的内涵

补码的实质

所谓补码,其实只是:非负数和规则①表示的负数,在二进制形式下的表示
所以虽然补码叫补码,但事实上它的本质和补字没有直接关联,它只是一种为了实现模数加法代替减法而构造出来的数字映射罢了。

补码并非在二进制中才有用,根据上面的定义,无论任何进制都不会改变补码体系的准确性。二进制与其它进制,影响只是求补码的简便方式(下面会提及)

补码最高位为符号位的解释

补码在二进制中的最高位为符号位,其实是因为规则②中,把半模以上的数用作表示负数,而恰好半模以上的数,在二进制表示中的最高位就是1,半模以下最高位是0

一篇彻底学懂补码

因此,从数字映射来讲,半模以上的正数确实被规则①映射为了负数;但是单论二进制数字而言,最高位的1仅代表它是半模以上的数,脱离了规则①它与正负符号没有任何关系。

总之,尽管在补码中,最高位确实可以简单地看做正负标志,但是需要注意的是,这种做法事实上有迹可循,千万不要想当然地以为这只是一种毫无根据的硬性规定

证明补码在加减运算的正确性

说了那么多,一直在被定义概念牵着走,我相信不少人会有一个疑问:做这么多都只是人为规定罢了,有没有证明补码在加减运算中正确性的途径?

虽然补码的制定上很巧妙,并不是一般人就能制定出这一套近乎完美的以加代减规则的,但是要证明补码的正确性,则相对于制定简单得多。

不严谨证明如下:
目标:由补码的实质,显然我们没有对非负数做任何调整,我们只是针对负数做了一个映射。如果我们能说明这种映射是可靠的,那么补码就是正确的。

前面也说了,补码从定义上就决定了不会因为进制改变而丢失正确性,因此以下用十进制形式说明

假设一个补码正数x,它的补码负数是y(即在补码中表示x相反数的数),在模 2 n 2^n 2n的情况下,我们只要能证明:对任意的正数x通过使用补码计算都有 ( x + y ) m o d 2 n = 0 (x + y)mod 2^n = 0 (x+y)mod2n=0,那么我们就说明了这种负数映射是可靠的,进而说明补码运算的正确。

由规则①: y = 2 n − x y = 2^n – x y=2nx
对任意x,有: ( x + y ) m o d 2 n = ( x + 2 n − x ) m o d 2 n = ( 2 n ) m o d 2 n = 0 (x + y)mod 2^n = (x + 2^n – x)mod 2^n =(2^n)mod 2^n = 0 (x+y)mod2n=(x+2nx)mod2n=(2n)mod2n=0
正数+它的相反数恒为0,这就说明了这种正数到负数的映射是正确的。

不过这个证明并不包括边缘值(最小负数),至于这个东西的补码,似乎就真的只是人为规定且恰好不违反规则①了()

原码到负数补码的转换

按位取反加一

上面基本讲解了补码的意义与本质,现在剩下的问题就是在二进制中:原码负数如何求补码?
我们总不能按规则①,依靠十进制定义来求负数表示,再转换成二进制吧?
我们希望的是找到一种原码直接转换成补码的形式

也就是我们喜闻乐见的“除符号位以外,按位取反加一”

为什么?

其实仍然是从规则①入手得到的规律:
设一个十进制数x的原码为: [ x ] 原 = 1 x 1 x 2 . . . x n [x]_原 = 1x_1x_2…x_n [x]=1x1x2...xn, 0 ≥ x > -2 n ^{n} n
则它的绝对值|x|的原码为: [ ∣ x ∣ ] 原 = 0 x 1 x 2 . . . x n [|x|]_原 = 0x_1x_2…x_n [x]=0x1x2...xn, 0 ≤ x < -2 n ^{n} n
则它的绝对值|x|的补码为: [ ∣ x ∣ ] 补 = 0 x 1 x 2 . . . x n [|x|]_补 = 0x_1x_2…x_n [x]=0x1x2...xn, 0 ≤ x < -2 n ^{n} n

根据规则①有: [ x ] 补 = ( 2 n + 1 ) D − [ ∣ x ∣ ] 补 [x]_补 = (2^{n+1})_D – [|x|]_补 [x]=(2n+1)D[x] (D表示十进制数)

统一为二进制,并转换为竖式计算:

1     0     0     0     . . . 0     − 0    x 1 x 2 . . . x n ‾ \begin{aligned} 1\;\, 0\;\, 0\;\, 0\;\, …0\;\, \\ \underline{- 0\;x_{1}x_{2}…x_{n}}\\ \end{aligned} 1000...00x1x2...xn

被减数拆为111…1 + 1得:

    1     1     1     . . . 1     +     1 − 0    x 1 x 2 . . . x n   ‾ 1    x ‾ 1 x ‾ 2 . . . x ‾ n +     1 \begin{aligned} \;\, 1\;\, 1\;\, 1\;\, …1\;\, + \;\,1\\ \underline{- 0\;x_{1}x_{2}…x_{n}\quad\quad\,}\\ 1\;\overline{x}_1\overline{x}_2…\overline{x}_n + \;\,1\\ \end{aligned} 111...1+10x1x2...xn1x1x2...xn+1

因此得到
[ x ] 补 = 1    x ‾ 1 x ‾ 2 . . . x ‾ n +   1 [x]_补 = 1\;\overline{x}_1\overline{x}_2…\overline{x}_n + \,1 [x]=1x1x2...xn+1
对比原码:
[ x ] 原 = 1 x 1 x 2 . . . x n [x]_原 = 1x_1x_2…x_n [x]=1x1x2...xn
恰好就得到了“符号位不变,其余按位取反加一”的结论

补码的定点加减法运算

最后回顾到补码本身的作用,考察补码是如何只用加法器实现加减法的。而对于乘除法,补码并没有太大优势,都是“硬件迎合补码”,而非如同加减那样“补码迎合硬件”,故不在此赘述。

补码加法公式

设x,y为两个十进制数,则有:
[ x ] 补 + [ y ] 补 = [ x + y ] 补 ( m o d   2 n + 1 ) [x]_补+[y]_补=[x+y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=[x+y](mod 2n+1)

补码加法正确性

分四种情况讨论。

首先由于保证运算结果不溢出,即约定范围:
∣ x ∣ < ( 2 n − 1 ) , ∣ y ∣ < ( 2 n − 1 ) , ∣ x + y ∣ < ( 2 n − 1 ) |x|<(2^n-1),|y|<(2^n-1),|x+y|<(2^n-1) x<(2n1),y<(2n1),x+y<(2n1)
(1) x > 0 , y > 0 x>0,y>0 x>0,y>0, 则 x + y > 0 x+y>0 x+y>0

相加两数都是正数,和也是正数。
正数补码的定义,用十进制表示有:
[ x ] 补 = x , [ y ] 补 = y , [ x + y ] 补 = x + y [x]_补=x,\quad[y]_补=y,\quad[x+y]_补=x+y [x]=x,[y]=y,[x+y]=x+y

故有:
[ x ] 补 + [ y ] 补 = x + y = [ x + y ] 补 ( m o d   2 n + 1 ) [x]_补+[y]_补=x+y=[x+y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=x+y=[x+y](mod 2n+1)
(2) x > 0 , y < 0 x>0,y<0 x>0,y<0, 则 x + y > 0 x+y>0 x+y>0 x + y < 0 x+y<0 x+y<0

相加两数一正一负,和符号不确定。
正、负数补码的定义,用十进制表示有:
[ x ] 补 = x , [ y ] 补 = 2 n + 1 − ∣ y ∣ = 2 n + 1 + y [x]_补=x,\quad[y]_补=2^{n+1}-|y| = 2^{n+1}+y [x]=x,[y]=2n+1y=2n+1+y

\quad (i) x + y > 0 x+y>0 x+y>0 ,则:

[ x + y ] 补 = x + y [x+y]_补=x+y [x+y]=x+y

\quad 故有:

[ x ] 补 + [ y ] 补 = x + 2 n + 1 + y = x + y = [ x + y ] 补 ( m o d   2 n + 1 ) [x]_补+[y]_补=x+2^{n+1}+y=x+y=[x+y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=x+2n+1+y=x+y=[x+y](mod 2n+1)
\quad (ii) x + y < 0 x+y<0 x+y<0 ,则:

[ x + y ] 补 = 2 n + 1 − ∣ x + y ∣ = 2 n + 1 + ( x + y ) [x+y]_补=2^{n+1}-|x+y|=2^{n+1}+(x+y) [x+y]=2n+1x+y=2n+1+(x+y)

\quad 故有:
[ x ] 补 + [ y ] 补 = x + 2 n + 1 + y = [ x + y ] 补 ( m o d   2 n + 1 ) [x]_补+[y]_补=x+2^{n+1}+y=[x+y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=x+2n+1+y=[x+y](mod 2n+1)
(3) x < 0 , y > 0 x<0,y>0 x<0,y>0, 则 x + y > 0 x+y>0 x+y>0 x + y < 0 x+y<0 x+y<0

同(2)可证,令x,y对调即可

(4)(2) x < 0 , y < 0 x<0,y<0 x<0,y<0, 则 x + y < 0 x+y<0 x+y<0

相加两数都是负数,和也是负数。
负数补码的定义,用十进制表示有:
[ x ] 补 = 2 n + 1 + x , [ y ] 补 = 2 n + 1 + y [x]_补=2^{n+1}+x,\quad[y]_补=2^{n+1}+y [x]=2n+1+x,[y]=2n+1+y

[ x + y ] 补 = 2 n + 1 − ∣ x + y ∣ = 2 n + 1 + ( x + y ) [x+y]_补=2^{n+1}-|x+y|=2^{n+1}+(x+y) [x+y]=2n+1x+y=2n+1+(x+y)

故有:
[ x ] 补 + [ y ] 补 = 2 n + 1 + x + 2 n + 1 + y = 2 n + 1 + ( x + y ) = [ x + y ] 补 ( m o d   2 n + 1 ) [x]_补+[y]_补=2^{n+1}+x+2^{n+1}+y=2^{n+1}+(x+y)=[x+y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=2n+1+x+2n+1+y=2n+1+(x+y)=[x+y](mod 2n+1)

综上所述:
无论x,y正负性如何,都有:任意两数的补码之和等于两数之和的补码,故补码加法公式成立

补码减法公式

[ x ] 补 − [ y ] 补 = [ x ] 补 + [ − y ] 补 = [ x − y ] 补 ( m o d   2 n + 1 ) [x]_补-[y]_补=[x]_补+[-y]_补=[x-y]_补\qquad(mod\ 2^{n+1}) [x][y]=[x]+[y]=[xy](mod 2n+1)

补码减法正确性

先证明: [ − y ] 补 = − [ y ] 补 [-y]_补=-[y]_补 [y]=[y]

由: [ x ] 补 + [ y ] 补 = [ x + y ] 补 ( m o d   2 n + 1 ) [x]_补+[y]_补=[x+y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=[x+y](mod 2n+1)

得: [ y ] 补 = [ x + y ] 补 − [ x ] 补 ( m o d   2 n + 1 ) ① [y]_补=[x+y]_补-[x]_补\qquad(mod\ 2^{n+1})\qquad① [y]=[x+y][x](mod 2n+1)

又由: [ x − y ] 补 = [ x + ( − y ) ] 补 = [ x ] 补 + [ − y ] 补 ( m o d   2 n + 1 ) [x-y]_补=[x+(-y)]_补=[x]_补+[-y]_补\qquad(mod\ 2^{n+1}) [xy]=[x+(y)]=[x]+[y](mod 2n+1)

得: [ − y ] 补 = [ x − y ] 补 − [ x ] 补 ( m o d   2 n + 1 ) ② [-y]_补=[x-y]_补-[x]_补\qquad(mod\ 2^{n+1})\qquad② [y]=[xy][x](mod 2n+1)

①+②得: [ y ] 补 + [ − y ] 补 = [ x + y ] 补 − [ x ] 补 + [ x − y ] 补 − [ x ] 补 = [ x + y + x − y ] 补 − [ x ] 补 − [ x ] 补 = [ x + x ] 补 − [ x ] 补 − [ x ] 补 = [ x ] 补 + [ x ] 补 − [ x ] 补 − [ x ] 补 = 0 ( 由 于 [ x ] 补 = [ x ] 补 可 得 [ x ] 补 − [ x ] 补 = 0 ) ( m o d   2 n + 1 ) \begin{aligned} [y]_补+[-y]_补&=[x+y]_补-[x]_补+[x-y]_补-[x]_补\\ &=[x+y+x-y]_补-[x]_补-[x]_补\\ &=[x+x]_补-[x]_补-[x]_补\\ &=[x]_补+[x]_补-[x]_补-[x]_补\\ &=0 (由于[x]_补=[x]_补可得[x]_补-[x]_补=0)\qquad(mod\ 2^{n+1})\\ \end{aligned} [y]+[y]=[x+y][x]+[xy][x]=[x+y+xy][x][x]=[x+x][x][x]=[x]+[x][x][x]=0([x]=[x][x][x]=0)(mod 2n+1)

即: [ − y ] 补 = − [ y ] 补 [-y]_补=-[y]_补 [y]=[y]

上式代入加法公式: [ x ] 补 + [ − y ] 补 = [ x − y ] 补 ( m o d   2 n + 1 ) [x]_补+[-y]_补=[x-y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=[xy](mod 2n+1)

得: [ x ] 补 + [ − y ] 补 = [ x ] 补 − [ y ] 补 = [ x − y ] 补 ( m o d   2 n + 1 ) [x]_补+[-y]_补=[x]_补-[y]_补=[x-y]_补\qquad(mod\ 2^{n+1}) [x]+[y]=[x][y]=[xy](mod 2n+1)

上式证明了补码减法公式的正确性,以及提供了以加代减的具体操作方式

[y]补 求 [-y]补 的法则

减法中需要以 [ y ] 补 [y]_补 [y] [ − y ] 补 [-y]_补 [y]实现以加代减,那么是不是有简便的转换法则呢?确实有的

法则:

包括符号位“按位取反再加一”

为什么?

设一个十进制数y的补码为: [ y ] 补 = a y 1 y 2 . . . y n [y]_补 = ay_1y_2…y_n [y]=ay1y2...yn,其中a为符号位
(1)若y>0,则a=0
y的原码为: [ y ] 原 = 0 y 1 y 2 . . . y n [y]_原 = 0y_1y_2…y_n [y]=0y1y2...yn
-y的原码为: [ − y ] 原 = 1 y 1 y 2 . . . y n [-y]_原 = 1y_1y_2…y_n [y]=1y1y2...yn

则:
-y的补码为: [ − y ] 补 = 1 y ‾ 1 y ‾ 2 . . . y ‾ n + 1 [-y]_补 = 1\overline{y}_1\overline{y}_2…\overline{y}_n+1 [y]=1y1y2...yn+1
对比y补码: [ y ] 补 = 0 y 1 y 2 . . . y n [y]_补 = 0y_1y_2…y_n [y]=0y1y2...yn

符合上述法则

(2)若y<0,则a=1
y的原码为: [ y ] 原 = 1 y ‾ 1 y ‾ 2 . . . y ‾ n + 1 [y]_原 = 1\overline{y}_1\overline{y}_2…\overline{y}_n+1 [y]=1y1y2...yn+1
(补码求原码也可以是符号位不变,其余按位取反加一,“取反加一与减一取反”在二进制中是等价的,有兴趣的可以百度)
-y的原码为: [ − y ] 原 = 0 y ‾ 1 y ‾ 2 . . . y ‾ n + 1 [-y]_原 = 0\overline{y}_1\overline{y}_2…\overline{y}_n+1 [y]=0y1y2...yn+1

则:
-y的补码为: [ − y ] 补 = 0 y ‾ 1 y ‾ 2 . . . y ‾ n + 1 [-y]_补 = 0\overline{y}_1\overline{y}_2…\overline{y}_n+1 [y]=0y1y2...yn+1
对比y补码: [ y ] 补 = 1 y 1 y 2 . . . y n [y]_补 = 1y_1y_2…y_n [y]=1y1y2...yn

符合上述法则

综上,该法则总是成立的

尾声

希望这篇缝合的文章对你有帮助

参考资料:
知乎:在8位二进制中,-128 没有原码、反码形式,那么它的补码是怎么计算出来的?还是约定的?——Simon Cao的回答

知乎:计算机中为什么可以用数值表示正负数?——伊尹的回答

计算机组成原理(第五版)白中英等著

今天的文章一篇彻底学懂补码分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/32274.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注