在計算機的底層是用0、1來表示資料，因此人類的符號系統要透過電腦表示就需要做編碼轉換，ASCII、Unicode等都是做此用途，而在(整數)數字系統的編碼，比較常見的有
- ASCII (將數字用ASCII表示)
- -200 => 2D 32 30 30
- BCD
- 189 => 01 08 09 (packed BCD)
- one’s complement (assume 8-bit size)
- 0 => 0000 0000b
- -0 => 1111 1111b (unsigned = 255)
- -1=> 1111 1110b (unsigned = 254)
- 127 => 0111 1111b
- -127=> 1000 0000b (unsigned = 128)
- two’s complement (assume 8-bit size)
- 0 => 0000 0000b
- -1 => 1111 1111b
- 127 => 0111 1111b
- -127 => 1000 0001b
unsigned integer的表示就是很單純的2進位轉換，但當考慮到負數的時候，就有不同的表示法，最直覺的想法就是加一個sign bit
例如:
127 = 0111 1111b
-127 = 1111 1111b
2 = 0000 0010b
-2 = 1000 0010b
但是這樣子的表示法在處理數字運算的時候，硬體的實作上比較麻煩且沒有一致性
因此產生了one’s complement / two’s complement表示法(signed number representation)
one’s complement是對positive number bit pattern做negate運算(1->0, 0->1)，two’s complement是在one’s complement的基礎上再offset 1 (negate 後 +1)
one’s complement: 1->0, 0->1 負號數字是 個別bit取1的補數
two’s complement: M + (-M) = 2^N 負號數字是取2^N的補數
現代的計算機在整數表示是以two’s complement，one’s complement system在早期的PDP-1、CDC6600等機器上使用，他的問題主要是整數數字0有兩種可能的表示法
one's complement calculations: -1 + 1 ==> 1111b 1111b ==> -0 (true for test zero) 6 - 19 => 6 + (-19) => 0000b 0110b + ~(0001b 0011b) 0000 0110 + 1110 1100 -------------------- 1111 0010 negative -> ~(0000 1101) = -13
看起來似乎one’s complement很單純就是按照一般bit加法運算的規則，並且相減就當成 加negate number，但事實上並不是這樣，有carry bit時需要特別處理
one's complement calculations with carry bit: 6 + (-0) => 0000 0110 + 1111 1111 -------------------- 1 00000101 5 with carry bit (expect 6)
在1’s complement運算，碰到carry bit，需要執行 end-around borrow，就是把1補到最後一個bit
1 00000101 5 with carry bit
=
00000101
+ 1
--------------------
00000110 = 6
再看
19 - 3 => 0001 0011 + 1111 1100 -------------------- 1 0000 1111 = 15 with carry bit (expect 16) => should wrap around 0000 1111 + 1 -------------------- 0001 0000 = 16
在硬體上就是一般的加法器再拉一個carry bit做加法就可以達成
跟two’s complement比，運算要另外處理carry bit，並且浪費了 negative zero的表示空間，two’s complement巧妙地做了offset 1解決上述兩個問題，addition, subtraction, multiplication 運算上跟unsigned integer方法一樣，
carry一律discard
127 = 01111 1111b
-127 = ~(0111 1111b) + 1
= 1000 0000b + 1
= 1000 0001b
15 - 5 0000 1111 + 1111 1011 ------------------- 1 0000 1010 = 10 with carry -2 + (-3) 1111 1110 + 1111 1101 ------------------- 1 1111 1011 = -5 with carry
two’s complement 的操作也可以這樣理解:
可以想像成 (以1 byte為例) 0 到 + 127 , -128 到 -1 的有限數字循環， 0000 0000 0 0000 0001 1 ... 0111 1111 127 1000 0000 -128 ... 1111 1110 -2 1111 1111 -1
每一個數字 +1 就會進到下一個數字 -N 代表退後 N步，也就是往前 256 - N步 1 0000 0000 - N = 1 + (1111 1111) - N = 1 + (1111 1111 - N) = 1 + ~N
因此 減N可以理解成往前 1 + ~N 步 也就是 加 1 + ~N
special case:
-N (負N) = 0 – N = 0 + 1 + ~N = 1 + ~N 也就是negate 再加1