Learning Objectives
- 寫出一位二進位加法的四種情況，說明為什麼和用 XOR、進位用 AND
- 說明半加器與全加器的差別，看懂全加器由兩個半加器與一個 OR 組成
- 說明漣波進位加法器如何把全加器串起來，以及進位傳遞造成的等待
- 分辨組合電路與循序電路
只有開關的電路，怎麼算出 5＋3
計算機的「計算」最基本就是加法：減法可以換成加上二補數（第 04 課），乘法可以拆成很多次加法與移位。 可是上一課的邏輯閘只會 AND、OR、NOT 這類「是／否」的判斷。這一課要回答：只用邏輯閘，怎麼做出會算加法的電路？
先回想小學的直式加法：從最右邊（個位）開始加，超過 9 就寫下個位數、把 1「進位」到左邊下一位。 二進位完全一樣，只是超過 1 就要進位：
0101 （5）
+ 0011 （3）
------
1000 （8）
最右邊 1＋1＝10（二進位），寫下 0、進位 1；下一位 0＋1＋進位 1＝10，又寫下 0、進位 1……進位一路往左傳。
一位數的加法：半加器
先只看一位數：兩個位元 A、B 相加，只有四種情況。結果最大是 1＋1＝2，二進位要兩位數 10，
所以輸出也要兩個位元：和（sum，S，個位數）與進位（carry，C）。
| A | B | A＋B | 進位 C | 和 S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 2 | 1 | 0 |
和上一課的真值表比一比：S 那一欄正好是 XOR（不一樣才是 1），C 那一欄正好是 AND（兩個都是 1）。 所以一個 XOR 加一個 AND，就是會算一位數加法的電路，叫半加器（half adder）。
三個數相加：全加器
直式加法從第二位開始，每一位要加三個數：A、B，以及右邊一位傳來的進位。三個輸入的加法器叫全加器（full adder），
輸入是 A、B、Cin（carry in），輸出是 S 與 Cout（carry out）。三個 1 相加等於 3，二進位是 11，兩個輸出就夠用。
全加器可以用兩個半加器組成：
- 第一個半加器算 A＋B，得到暫時的和 A ⊕ B 與進位 A · B。
- 第二個半加器把暫時的和再加上 Cin，得到最後的 S ＝ A ⊕ B ⊕ Cin。
- 兩個半加器都可能產生進位，用一個 OR 合起來：Cout ＝ A · B ＋ (A ⊕ B) · Cin。
S ＝ A XOR B XOR Cin
Cout ＝ (A AND B) OR ((A XOR B) AND Cin)
把全加器串起來：漣波進位加法器
要加 4 位元的數，就準備 4 個全加器，每一位一個，把每一位的 Cout 接到左邊下一位的 Cin；最低位的 Cin 接 0。 這叫漣波進位加法器（ripple-carry adder）：進位像水波一樣，一位一位往左傳。
下面的程式用同樣的公式，模擬 4 個全加器從最低位算到最高位。注意程式裡的串列是從最低位排到最高位，
所以 5（二進位 0101）寫成 [1, 0, 1, 0]。
用程式模擬 4 位元加法
^ 是 XOR、& 是 AND、| 是 OR。每一圈就是一個全加器：用 a[i]、b[i] 和進來的 carry 算出這一位的和 s[i]，再算出要傳給下一位的進位。看上方的格子：i 指到哪一位，s 就填上哪一位。
想一想：半加器與全加器
全加器的輸入 A＝1、B＝0、Cin＝1，輸出 Cout 與 S 各是多少？
下面這段程式模擬一個全加器，會印出什麼？
a, b, c = 1, 1, 1
s = a ^ b ^ c
cout = (a & b) | (c & (a ^ b))
print(cout, s)
半加器和全加器最主要的差別是什麼？
組合電路與循序電路
這兩課做的電路有一個共同點：輸出只由「現在的輸入」決定，同樣的輸入永遠得到同樣的輸出，電路本身不記得過去。 這種電路叫組合電路（combinational circuit），例如加法器、比較兩個數是否相等的比較器、依編號選一條線輸出的多工器。
如果把輸出再接回輸入，電路就能「記住」一個位元，輸出會受到過去的輸入影響，這叫循序電路（sequential circuit）， 例如正反器（flip-flop）、暫存器、計數器。CPU 裡的暫存器與記憶體就建立在這種會記憶的電路上（第 10 課以後會用到）。
| 組合電路 | 循序電路 | |
|---|---|---|
| 輸出由什麼決定 | 只看現在的輸入 | 現在的輸入＋記住的狀態 |
| 例子 | 加法器、比較器、多工器 | 正反器、暫存器、計數器 |
另外，漣波進位加法器的缺點是位數越多、進位要傳越久。實際的處理器會用超前進位（carry-lookahead）等設計， 用更多的閘提前算出每一位會不會收到進位，以空間換取時間。
想一想：串接與延遲
4 位元漣波進位加法器計算 0111＋0001，哪一個全加器的結果最晚確定？
4 位元無號數相加 1100＋0110（12＋6），4 個和的位元 S3S2S1S0 與 Cout 是什麼？
下列哪一個是循序電路？
重點整理
- 一位數的二進位加法：和 S＝A XOR B，進位 C＝A AND B，這就是半加器。
- 全加器多一個進位輸入 Cin：S＝A ⊕ B ⊕ Cin，Cout＝A · B ＋ (A ⊕ B) · Cin；可以用兩個半加器加一個 OR 組成。
- 漣波進位加法器把 n 個全加器串起來，每一位的 Cout 接到下一位的 Cin；最壞情況要等進位從最低位傳到最高位，位數越多越慢。
- 結果超過位元數能表示的範圍時，多出來的一位在最高位的 Cout，只看 S 就會溢位。
- 輸出只看現在輸入的是組合電路；能記住狀態的是循序電路，是暫存器與記憶體的基礎。
下一課：有了會計算的電路，還要有記憶體、控制單元，才組成一台電腦：馮紐曼架構與指令週期。