背景
大家都知道计算机内部采用补码表示整数的,但是具体到补码的内在含义,很多人不能理解,故我们分享自己的理解。
首先说下补码的定义以及基本性质:
1) 正数的补码和原码相同;
2) 负数的补码等于取反后加1;
3) 0的正负两种补码相同;
4) 对一个补码再求补码等于自己;
5) 一个正数的原码和其对应的负数的补码相加等于模;
针对本文,我们其实只关心规则1)和2)即可。
--------------------------------------------------------------------------------
实例
为方便说明现有的补码定义(即正数的补码等于原码;负数的补码等于取反加1),本文均以八进制为例。
5 – 3 //记作式A,方便后文引用
= 5 + ( -3 )
(下面开始转为二进制补码格式)
= 0101 + ( 1111 – 0011 + 1 ) //展开-3的补码形式
= ( 0101 – 0011 ) + ( 1111 + 0001 ) //交换
= ( 0101 – 0011 ) + ( 0000 ) //此处10000溢出为0000
= 0010 //得出结果是2的补码,也是2的原码1
2 – 3 //记作式B,方便后文引用
= 2 + ( -3 )
(下面开始转为二进制补码格式)
= 0010 + ( 1111 – 0011 + 0001 ) //展开-3的补码形式
= 1111 – ( 0011 – 0010 ) + 0001 //交换
= 1111 – 0001 + 0001
= 1111 //得出结果是-1的补码1
由式A和式B,我们可以获得一个感性认识了。我们放宽到更一般的情况,(X和Y为任意正整数):
X – Y //记作式C,方便后文引用
= (X的补码) + ((-Y)的补码) //计算机将这样的两个补码将加
(如果X>Y,由式A可以推得=(X – Y )的补码;
如果X<Y,由式B可以推得=(-(Y-X))的补码;
最终归结,就是=(X-Y)的补码!)
= (X-Y)的补码 //不管(X-Y)是正还是负,都成立!别忘了正数的补码就是原码。1
可见,计算机内部是在对X和(-Y)计算两个补码之和,而实际得出的结果是(X-Y)的补码,正是我们所期望的!
至此,我们知道现有的补码机制确实是正常工作的!
--------------------------------------------------------------------------------
扩展
上述我们采用的补码定义是众所周知的(即正数的补码等于原码;负数的补码等于取反加1)。那么我们的问题来了,补码定义可以修改么?
我们针对八进制具体看下补码定义:(X为正数)
正数X的补码等于X的原码;(此处可理解为正数X的补码等于X+K,K=0000)
负数(-X)的补码等于M-X+N,M=1111,N=0001;
我们的问题就是这里的K、M、N是可以修改成别的值么?
我们尝试修改M和N:M=1100,N=0100。我们发现,这样的M和N对于式A和式B是没问题的!那为何不采用呢?其实原因很简单,但很致命:电路硬件实现取反(效果就是1111-X)很容易,但是实现1100-X这种形式的就又陷入减法计算了。毕竟我们的初衷是希望减法也能采用加法器完成,这也是我们采用引入补码编码整数的原因!
好吧,我们保持M=1111,接着尝试修改N=0010,也就是将负数的补码定义修改为取反加2。我们发现,对于式B是没有问题的,但是式A不满足了!其实如果此时我们同时修改正数的补码定义为原码加1(正数X的补码修改为X+1),就能满足式A了,不信的话就请试试。除了得修改正数补码定义之外,还同时引入了一个映射的新问题!我们期望是[-8,-1]整个区间是可以一一映射到1XXX形式的补码上,共8个数。而我们这么修改后,-1的补码变成了0000,而0的补码也是0000;7的补码反倒是1000了。所以不仅一一映射被破坏了,负数的首bit为1的补码形式也破坏了!
那我们如果保持M=1111,修改N=0000呢?也就是将负数的补码定义修改为仅仅取反。我们发现,此时1111和0000都是0的补码表示(此时规定任意一种即可),而-8则没有对应的补码。可见,此时仅仅浪费了一个补码表示(-8)而已。事实上,过去有些厂家就是这么实现的。如果查看c语言标准,可以看到其实浪费(对于我们的例子就是-8)是允许的。
现在可以推导一下了,假设X为正数,原码X的定义为X+K,补码(-X)的定义为M-X+N,此时式C就变成了:
X - Y //记作式D,方便后文引用
= X + (-Y)
(下面开始转为二进制补码格式)
= X + K + ( M - Y + N )
(如果X>Y,= K + M + N + (X-Y)。
此时分析正数(X-Y)的补码并根据正数补码定义可以推出:
K + M + N = K,即M + N = 0。
如果X<Y,= M - (Y-X)+ K + N。
此时分析负数(X-Y)的补码并根据负数补码定义可以推出:
K+N=N,即K为0)
最终我们得出M + N = 0,K = 0。而根据硬件易于实现反码的事实,M = 1111。故
M = 1111
N = 0001
K = 00001
--------------------------------------------------------------------------------