二補數

维基百科,自由的百科全书
跳转至: 导航搜索
符號
0 1 1 1 1 1 1 1 = 127
0 0 0 0 0 0 1 0 = 2
0 0 0 0 0 0 0 1 = 1
0 0 0 0 0 0 0 0 = 0
1 1 1 1 1 1 1 1 = −1
1 1 1 1 1 1 1 0 = −2
1 0 0 0 0 0 0 1 = −127
1 0 0 0 0 0 0 0 = −128

二补数2's complement)是一種用二進位表示有號數的方法,也是一種將數字的正負號變號的方式,常在計算機科學中使用。在中國大陸稱作补码,台湾和香港称为二补数

一個數字的二补数就是將該數字作位元反相運算(即一補數反码),再將結果加 1。在二补数系統中,一個負數就是用其對應正數的二补数來表示。

二补数系統的最大優點是可以在加法減法處理中,不需因為數字的正負而使用不同的計算方式。只要一種加法電路就可以處理各種有號數加法,而且減法可以用一個數加上另一個數的二补数來表示,因此只要有加法電路及二补数電路即可完成各種有號數加法及減法,在電路設計上相當方便。

另外,二补数系統的 0 只有一個表示方式,這點和一補數系統不同(在一補數系統中,0 有二種表示方式),因此在判斷數字是否為 0 時,只要比较一次即可。

右側的表是一些 8-bit 二补数系統的整數。它的可表示的範圍包括-128到127,總共256 (28)個整數。

數字表示方式[编辑]

說明[编辑]

二补数 十進位
0111 7
0110 6
... ...
0010 2
0001 1
0000 0
1111 −1
1110 −2
... ...
1001 −7
1000 −8

以下用 4 位元的二补数數字來說明二补数系統的數字表示方式。

  • 在表示正數和零時,二补数數字和一般二進位一樣,唯一的不同是在二补数系統中,正數的最高位元恆為 0,因此4 位元的二补数正數,最大數字為 0111 (7)。
  • 二补数數字的負數,最高位元恆為 1,4 位元二补数的數字中,最接近 0 的負數為 1111 (-1),以此類推,因此絕對值最大的負數是 1000 (-8)。

以上的表示方式在電腦處理時格外方便,用以下的例子說明:

  0011  (3)
  + 1111 (-1)
--------------
   10010  (2)

結果 10010 似乎是錯的,因為已經超過四個位元,不過若忽略掉(從右數起的)第 5 個位元,結果是 0010 (2),和我們計算的結果一樣。而且若可以將二進位的 0001 (1) 變號為 1111 (-1),以上的式子也可以計算減法:3-1 = 2。

在 n 位元的二补数加減法中,忽略第 n+1 個位元的作法在各種有號數加法下都適用(不過在判斷是否溢位(overflow)時,仍然會用到第 n+1 個位元)。因此在二补数的系統,加法電路就可以處理有負數的加法,不需另外處理減法的電路。而且,只要有電路負責數字的變號(例如將 1 變換為 -1),也可以用加法電路來處理減法。而數字的變號就用計算數字的二补数來完成。

在一般 n 位元的二進位數字中,最高有效位元(MSB) 第 n 位元代表的數字為 2n−1。不過,在 n 位元的二补数系統中,最高有效位元(MSB) 第 n 位元表示符號位元,若符號位元為 0,數字為正數或 0,若符號位元為 1,數字為負數。以下是 n 位元的二补数系統中,幾個特別的數字:

二补数 實際數字 附註
0 111....111 2n−1-1 最大正數
... ...
0 000....001 1
0 000....000 0
1 111....111 -1
... ...
1 000....001 -2n−1+1
1 000....000 -2n−1 最小負數

因此,在 8 位元的二补数系統中,可以表示的最大正數為 28−1-1 = 127,可以表示最小的負數為 -28−1 = -128 

計算二补数[编辑]

在計算二進制數字的二补数時,會將數字進行位元反相運算,再將結果加 1,不考慮溢位位元(一般情形,溢位位元會為 0),就可以得到該數字的二补数。

以下考慮用有號數 8 位元二進位表示的數字 5:

0000 0101 (5)

其最高位元為 0,因為此數字為正數。若要用二补数系統表示 -5,首先要將 5 的二進位進行反相運算〔1 變為 0,0 變為 1 〕:

1111 1010

目前的數字是數字 5 的一補數,因此需要再加 1,才是二补数:

1111 1011 (-5)

以上就是在二补数系統中 -5 的表示方式。其其最高位元為 1,因為此數字確實為負數。

一個負數的二补数就是其對應的正數。以 -5 為例,先求數字的一補數:

0000 0100

再加一就是 -5 的二补数,也就是 5。

0000 0101 (5)

簡單來說,數字 a (正負數皆可)的二补数即為 -a。

若要計算 n 位數二补数二進位對應的十進位,需要知道每位數對應的數字,除了最高位元外,其他位元的對應數字均和一般二進位相同,即第 i 位數表示數字 2i−1。但最高位元若為 1 時,其表示數字為 -2n−1,因此若用此方式計算 0000 0101 表示的數字,其結果為:

1111 1011 (−5) = −128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 = (−27 + 26 + ...) = −5

特別的數字[编辑]

有二個數字的二补数等於本身:一個是 0,另一個為該位元可表示最大絕對值負數(即 1000...)。

0 的二补数計算方式(以 8 位元為例) 如下:先計算它的一補數:

1111 1111

再將一補數加一:

0000 0000, 溢位位元 = 1

忽略溢位,其結果為 0(0 是唯一計算二补数過程中會出現溢位的數字。)。因此 0 的二补数為 0。而 0 x (-1) = 0,因此其二补数仍滿足「數字 a 的二补数為 -a」的原則。

若計算 1000 0000 (-128、8 位元可表示最大絕對值負數)的二补数:先計算它的一補數:

0111 1111

再加一就是它的二补数。

1000 0000

1000 0000 (-128)的二补数仍為 1000 0000 (-128)。但 (-128) x (-1) = 128,因此其二补数是以上規則的例外。

其例外原因為因為 8 位元的二补数數字範圍為 -128 ~ 127。128 無法以 8 位元的二补数數字表示。在計算其他位數的最大絕對值負數(即 1000...000)時,也會有類似情形。

其他計算方法[编辑]

方法一[编辑]

另一種正式計算一數字(以 -N 為例)的二补数 N* 的公式如下:

N^*  = 2^n - N

其中 N* 是 -N 的補數,而 n 是數字 -N 用二進位表示時需要的位數。

以八位元的「-123」為例:

n = 8
N = +123(10) = 111 1011(2) (扣除表示正負號的第一個位,實際只有七個位可用)

-123 的二补数計算方式如下:

N^* = 2^n - N = {2^8}_{(10)} - 111\ 1011 = 1\ 0000\ 0000 - 111\ 1011 = 1000\ 0101
-123_{(10)} = 1000\ 0101_{(2)}
驗證
-123=-128+5=1000\ 0000 + 101 = 1000\ 0101

方法二[编辑]

以另一種較簡單的方式,可以找出二進位數字的二补数:

  • 先由最低位元開始找。
  • 若該位元為 0,將二补数對應位元填 0,繼續找下一位元(較高的位元)。
  • 若找到第一個為 1 的位元,將二补数對應位元填 1。
  • 將其餘未轉換的位元進行位元反相,將結果填入對應的二补数。

以 0011 1100 為例(圖中的 ^ 表示目前轉換的數字,-表示還不確定的位數):

   原數字       二补数
 0011 1100  ---- ---0    (此位元為 0) 
         ^

 0011 1100  ---- --00    (此位元為 0) 
        ^

 0011 1100  ---- -100    (找到第 1 個為 1 的位元) 
       ^

 0011 1100  1100 0100    (其餘位元直接反相) 
 ^

因此其結果為 1100 0100

符號延展[编辑]

十進位 4 位元二补数 8 位元二补数
5 0101 0000 0101
-3 1101 1111 1101

將一個特定位元二补数系統的數字要以較多位元表示時(例如,將一個位元組的變數複製到另一個二個位元組),所有增加的高位元都要填入原數字的符號位元。在一些微處理機中,有指令可以執行上述的動作。若是沒有,需要自行在程式中處理。==>

在二补数系統中,當數字要向右位移幾個位元時,在位移後需將符號位元再填入原位置(算术移位),保持符號位元不變。以下是二個例子:

    數字      0010 1010             1010 1010
向右位移一次  0001 0101             1101 0101
向右位移二次  0000 1010             1110 1010

而當一個數字要向左位移n個位元時,最低位元填n个 0,权值最高的n个位被抛弃。以下是二個例子:

    數字      0010 1010             1010 1010
向左位移一次  0101 0100             0101 0100
向左位移二次  1010 1000             1010 1000

向右位移一次相當於除以 2,利用算术移位的方式可以確保位移後的數字正負號和原數字相同,因為一數字除以 2 後,不會改變其正負號。 注意:向左位移一次相當於乘以2,虽然乘以在理论上并不会改变一个数的符号,但是在二补数系统中,用以表示数的二进制码长度有限,能够表示的数的范围也是有限的:若一个数的高权值上的数位已经被占用,此时再将这个数左移若干位(乘以2n)的话,有可能造成数位溢出(overflow),高权值上的数将会失去,对于绝对值很大数,这将造成整体表达的错误。

二补数的工作原理[编辑]

为什么二补数能这么巧妙实现了正负数的加减运算?答案是:指定n位元字长,那么就只有2n个可能的值,加减法运算都存在上溢出与下溢出的情况,实际上都等价于2n的加减法运算。这对于n位元无符号整数类型或是n位元有符号整数类型都同样适用。

例如,8位元无符号整数的值的范围是0到255. 因此4+254将上溢出,结果是2,即(4+254) \equiv 258 \equiv 2 \pmod{256}

例如,8位元有符号整数的值的范围,如果规定为−128到127, 则126+125将上溢出,结果是−5,即(126+125) \equiv 251 \equiv -5 \pmod{256}

对于8位元字长的有符号整数类型,以28即256为模,则


\begin{align}
-128 & \equiv 128 \pmod{256} \\
-127 & \equiv 129 \pmod{256} \\
\vdots \\
-2 & \equiv 254 \pmod{256} \\
-1 & \equiv 255 \pmod{256} \\
\end{align}

所以模256下的加减法,用0, 1, 2, …, 254,255表示其值,或者用−128, −127,… , −1, 0, 1, 2,… ,127是完全等价的。−128与128,−127与129,…,−2与254,−1与255可以互换而加减法的结果不变。从而,把8位元(octet)的高半部分(即二进制的1000 0000到1111 1111)解释为−128到−1,同样也实现了模256的加减法,而且所需要的CPU加法运算器的电路实现与8位元无符号整数并无不同。

实际上对于8比特的存储单元,把它的取值[00000000, …, 11111111]解释为[0, 255], 或者[-1, 254], 或者[-2, 253], 或者[-128, 127], 或者[-200, 55], 甚至或者[500, 755], 对于加法硬件实现并无不同。

運算[编辑]

加法[编辑]

二补数系統數字的加法和一般加法相同,而且在運算完成後就可以看出結果的正負號,不需特別的處理。

正數與負數相加不會出現上溢錯誤,上溢錯誤只會在兩個正數或兩個負數相加時發生。

以 15 加 -5 為例:

 11111 111   (进位)
  0000 1111  (15)
+ 1111 1011  (-5)
==================
  0000 1010  (10)

由於加數和被加數都是 8 位元,因此運算結果也限制在 8 位元內。第 8 位元相加後產生的進位不考慮(因為不存在第 9 位元)的 1 被忽略,所以其結果為 10。而 15 + (-5) = 10,計算結果正確。

在以上計算式中,可以由進位列的最左側二個位元得知結果是否出現溢位。溢位就是數字的絕對值太大,以致於無法在指定的二進位位元個數來表示(在此例中,是超過 8 位元的範圍)。若進位列的最左側二個位元同為 0 或同為 1,表示結果正確,若是一個為 0,另一個為 1,表示出現溢位錯誤。也可以對此二個位元進行异或運算,結果為 1 時,表示出現溢位錯誤。以下以 7 + 3 的 4 位元加法說明溢位錯誤的情形。

 0111   (进位)
  0111  (7)
+ 0011  (3)
=============
  1010  (−6)  結果不正確!

在此例中,進位列的最左側二個位元為 01,因此出現溢位錯誤。溢位的原因是 7 + 3 的結果 (10) 超過二补数系統 4 位元所可以表示的數字範圍 -8~7。

減法[编辑]

乘法[编辑]