106.10.13 二進位運算 (binary operations)

沒認真整理還真的不會懂
覺得慚愧....
就來個難得長篇(我用了兩天寫，當然不是整整兩天OuO)
106.10.14 新增十進位轉成二進位方法

有錯誤請告知我QuQ

對了，針對這個我有用 Rust 實作一個 8-bit 的加減法器
傳送門在此 ( code 在 src/main.rs 裡

進入正題：

有無號

首先二進位有分成無號數(Unsigned)、有號數(Signed)
以 4-bit 為例
無號範圍：0 ~ 15
有號範圍：-8 ~ 7   (本篇以最常用的二補數 two's complement 表示)

無號就是把 4 個位元皆來表示數字
e.g. 1001₂ = 9₁₀
而有號則會把有一位表示正負
e.g. 1001₂ =  -7₁₀

二補數

同樣記錄一下二補數
二補數是表示有號數的一種方式
算法為 A 的二補數 = 2ⁿ - A
e.g. 1001₂ 的二補數為 10000₂ - 1001₂ = 0111₂

更好的記法是 "二補數就是一補數加一"
主要是因為一補數會出現 -0 (1111₂)，加 1 之後剛好會溢位成 0000₂
如此就可以去掉 -0 的情況，並且可以多表示一個數字

現在又要先講一補數
某二進位的一補數就是其所有位元的0、1互換
e.g. 1011₂ 的一補數是 0100₂

而二補數就是再加1
e.g. 1011₂ 的二補數是 0100₂ + 0001₂ = 0101₂

而剛好最左位是 0 就是正數(或 0)，是 1 為負數
而剛好相反數互為補數，1000₂ 例外   e.g. 3 (0011₂)、-3 (1101₂)

無號數轉成十進位

從左到右分別代表2³、2²、2¹、2⁰
e.g. 1001₂ = 1 * 2³ + 0 * 2² + 0 * 2¹ + 1 * 2⁰ = 9₁₀

十進位轉成無號數

最常見是用除法找餘數，看是幾個 bit 就除以幾次 2，越晚出現的餘數就越左位
e.g.
7 ÷ 2 = 3 … 1
3 ÷ 2 = 1 … 1
1 ÷ 2 = 0 … 1
0 ÷ 2 = 0 … 0
7₁₀ = 0111₂

4 ÷ 2 = 2 … 0
2 ÷ 2 = 1 … 0
1 ÷ 2 = 0 … 1
0 ÷ 2 = 0 … 0
4₁₀ = 0100₂

但若是平常運算或想用看的來轉換的話可以用減法
透過最靠近又不大於的 2 的次方倍把原數拆開
e.g.
13 - 8 = 5
5 - 4 = 1
如此就可以知道 13₁₀ = 8 + 4 + 1 = 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 1101₂
然後減法其實可以心算，如此就不用除以好幾次 2 了

有號數(二補數)轉成十進位

我的方法是先由最左位判斷正負
若是 0 (正數) 則同無號數轉十進位那樣
若是 1 (負數) 則先進行二補數，再將結果當成無號數轉成十進位，最後乘上 (-1)
原理算式：-A = - (2ⁿ - (2ⁿ - A))
e.g. 1001₂ ─> 二補數 ─> 0111₂ = 7₁₀ ─> 乘以(-1) ─> -7₁₀
用原理解釋：(可直接使用相反數互為補數)
若求出 1001₂ 是某數 A 的二補數，則 1001₂ 就是 -A
所以令 1001₂ 是 2n - A (A 的二補數)
用 2⁴ - (2⁴ - A) 就會得到 A
所以 A = 2⁴ - 1001₂ = 0111₂ = 7₁₀
因此 1001₂ = -A = -7₁₀

十進位轉成有號數

同樣先判斷正負，是正的就跟十進位轉成無號數相同
是負的就需要先乘上 (-1)，接著使用十進位轉成無號數，最後進行二補數
e.g. -4₁₀ ─> 乘以(-1) ─> 4₁₀ ─>轉換 ─> 0100₂ ─> 二補數 ─> 1100₂

無號數加法

以 4-bit 為例，即為 0 (0000₂) ~ 15 (1111₂) 間的加法
一般加法沒問題

   0011 (3)
+) 0101 (5)
──────────
   1000 (8)

但需要注意溢位 (Overflow)
就是加完之後大於可以存放的大小
e.g. 超出的會直接被捨棄

   1001 (9)
+) 1000 (8)
──────────
  10001 (1) // 不是 17
  ^
  └─── 溢位

無號數減法

使用二補數來實現
原理算式：A - B = A + (2ⁿ - B) - 2ⁿ
e.g. 7 - 5 = 7 + (5的二補數) = 2

   0111 (7)
-) 0101 (5)
──────────
   0111 (7)
+) 1011 (5 的二補數)
──────────
  10010
-)10000 (2n)
──────────
   0010 (2)

若是小 - 大雖然會出現負數 (overflow) 亦可透過外加負號表示
原理算式：A - B = - {2ⁿ - [A + (2ⁿ - B)]}
e.g. 5 - 7 = - {[7 + (5的二補數)]的二補數} = -2

   0101 (5)
-) 0111 (7)
──────────
   0101 (5)
+) 1001 (7 的二補數)
──────────
   1110
   0010 (取二補數後為 2，代表答案是 -2)

有號數加法

以 4-bit 為例，即為 -8 (1000₂) ~ 7 (0111₂) 間的加法
e.g. 5 + (-2) = 3

   0101 (5)
+) 1110 (-2)
──────────
  10011 (3)
  x

有號數減法

一樣透過二補數
e.g. 5 - (-2) = 5 + 2 = 7

   0101 (5)
-) 1110 (-2)
──────────
   0101 (5)
+) 0010 (-2 的二補數 = 2)
──────────
   0111 (7)

有號數加減溢位

這還蠻重要的所以拉出來獨力說明
如果有注意到有號數加法範例中的 x 就會發現結果明明就溢位，但是直接去掉卻是正解
其實有號數在計算時需要多加一位作 carry
平常不會用到
但在某些運算可能會出現溢位，這時就要請出這個 carry 來判斷是否真的有溢位
上句某些運算有這些情況：正 + 正、負 + 負、正 - 負、負 - 正，除了這些其他必定不會溢位
所以有號數加法範例中的 x 就可以直接忽略不看
而溢位判定就是要比較 carry 和結果的最左位，相同表示沒溢位，不同就代表發生溢位了
原理：就是判斷有沒有變號，不相同就是變號
           而因為無法存放多出來的符號，就會出現明明應該是負的卻顯示正的
e.g. -5 - 6 = -11 (-11 < -8 ─> 溢位)

   1011 (-5)
-) 0110 (6)
──────────
   1011 (-5)
+) 1010 (6 的二補數 = -6)
──────────
  10101 (5) // 不是 -11
  ^^
  │└ 最左位
  └─ carry ─> 不相同 ─> 溢位

e.g. -5 - 2 = -7 (-7 > -8 ─> 無溢位)

   1011 (-5)
-) 0010 (2)
──────────
   1011 (-5)
+) 1110 (2 的二補數 = -2)
──────────
  11001 (10012 = -710)
  ^^
  │└ 最左位
  └─ carry ─> 相同 ─> 無溢位