2's complement

真是糟糕，這些基本的都遺忘了。

http://www.programmer-club.com.tw/ShowSameTitleN/c/40792.html


在十進位的寫法裡, 「負十二」的寫法是 -12, 用二進位來寫, 是 -1100. 這是數學上的概念.

問題是, 當數學上的概念要應用到電腦上時, 我們要用什麼方法來表示「負」這個概念.


 當然我們需要多一個 bit, 來表示「正」或「負」. 這個 bit 就叫作 sign bit. 其餘的代表數值大小的位元就叫 value bits.

接下來要決定的是 sign bit 的值所代表的意義. 為了符合數學上的概念, 用 0 來代表正值, 1 表示負值.

接下來要決定的是: 當 sign bit 等於 1 的時候, value bits 的意義. 有三種表示法 (方刮號表示 sign bit, 後面的是 value bits):

1. signed magnitude. Value bits 的值跟正數相同
[0] 1100 : 12
[1] 1100 : -12

2. 1's complement, 把 value bits 的值取 not.
[0] 1100 : 12
[1] 0011 : -12

3. 2's complement. 1's complement 後再加1:
[0] 1100 : 12
[1] 0100 : -12


正值都是一樣的, 只是負值各有不同的表示法. 這三種都是 C 及 C++ 語言標準所允許的.

目前大部份的系統都採用 2's complement 的表示法. 在這個表示法裡, sign bit 是在最左邊, 計算時把它當作負值, 比方說:

[1]0100 = -1*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 0*2^0
= -16 + 4
= -12

它有幾個好處:
- 當位元的數目增加時, 只需把 sign bit 裡的值往左邊複製:
十進位的 12:
Value bit 4 位元 : [0] 1100
Value bit 8 位元 : [0] 00001100
Value bit N 位元 : [0] 0...0001100

十進位的 -12:
Value bit 4 位元 : [1] 0100
Value bit 8 位元 : [1] 11110100
Value bit N 位元 : [1] 1...1110100

以 [1]11110100 來說, 它的數值是:

-1*2^8 + 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 0*2^0
= -256 + 128 + 64 + 32 + 16 + 0 + 4 + 0 + 0
= -12


- 減法跟加法是同樣的邏輯.

5 - 12 = 5 + (-12)
= [0]0101 + [1]0100
= [1]1001
= -1*2^4 + 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0
= -16 + 8 + 0 + 0 + 1
= -7