在計算機的底層是用0、1來表示資料，因此人類的符號系統要透過電腦表示就需要做編碼轉換，ASCII、Unicode等都是做此用途，而在(整數)數字系統的編碼，比較常見的有
- ASCII (將數字用ASCII表示)
- 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
