歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

深入理解二進制補碼

背景
大家都知道計算機內部采用補碼表示整數的,但是具體到補碼的內在含義,很多人不能理解,故我們分享自己的理解。

首先說下補碼的定義以及基本性質:
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

--------------------------------------------------------------------------------

結論
現在我們可以重新審視補碼機制了。其實就是利用硬件電路容易實現的取反變通地實現了減法,在實現時充分考慮了一一映射原則以及保證負數的補碼是首bit位為1的形式。

Copyright © Linux教程網 All Rights Reserved