Learning Objectives
- 用閘接出半加器與全加器，說明進位怎麼產生
- 把全加器串成 4 位元漣波進位加法器
- 用二補數與 XOR 控制反相，讓同一個加法器也會做減法
- 判斷有號數加法有沒有溢位，並接出偵測電路
- 用多工器把幾種運算組成 1 位元 ALU
直式加法的每一格，都是同一個小問題
用紙筆算 27 + 35 時，你從個位開始：7 + 5 ＝ 12，寫 2 進 1；再算十位：2 + 3 再加上進位的 1。不管數字多長，每一格做的事都一樣：兩個數字加上一個進位，得到這一格的答案與新的進位。
二進位更簡單，每一格只有 0 和 1。只處理兩個位元、不管進位的電路叫半加器（half adder）：
| A | B | 進位 C | 和 S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
看兩個輸出的欄位，正好是兩個認識的閘：S = A ⊕ B、C = A·B。
全加器：把進位也算進來
從第二格開始就要處理進位輸入 Cin，所以需要三個輸入的全加器（full adder）。可以把它想成兩步：
- 先把 A、B 相加：半和
X = A ⊕ B，同時可能產生進位A·B - 再把 Cin 加進半和：
S = X ⊕ Cin，這一步也可能產生進位X·Cin
兩步不會同時進位（第一步進位時 X 一定是 0），所以 Cout = A·B + X·Cin。一共 5 個閘：兩個 XOR、兩個 AND、一個 OR。
三個輸入裡有奇數個 1 時 S 是 1，有兩個以上的 1 時 Cout 是 1。後者你在上一課見過：就是多數決。
把全加器串起來
每一位放一個全加器，把上一位的 Cout 接到下一位的 Cin，這就是漣波進位加法器（ripple-carry adder）：進位像水波一樣一位一位傳上去。
往後的電路太大，我們用包裝好的 fa 元件。每個 fa 內部就是你剛才接的 5 個閘，只是在模擬器裡算一個延遲。
最低位的 Cin 平常接 0。為什麼還要留這支腳？等一下做減法會用到它。下面的練習會把進位鏈和減法一起接。
減法不需要另一個電路
4 個位元有 16 種組合。如果要表示負數，常用的規則是二補數（two's complement）：最高位的權重是負的。4 位元的 1011 是 −8 + 2 + 1 ＝ −5，範圍是 −8 到 7。
要求一個數的負數，只要全部反相再加 1：
5 = 0101
反相 1010
加 1 1011 = -5
好處在這裡：同一個加法器可以直接算有號數。A − B 就是 A + (−B)，也就是 A + B′ + 1。B′ 用反相器做得到，多出來的 1 從最低位的 Cin 塞進去：那支腳就是留給這件事的。
要讓同一個電路可切換加減，不能把 NOT 焊死。這時 XOR 派上用場：B ⊕ 0 = B、B ⊕ 1 = B′。把 XOR 當成「可控制的反相器」，再用一條 SUB 訊號同時控制所有 XOR 與最低位的 Cin：
| SUB | 每一位的 B 輸入 | 最低位 Cin | 結果 |
|---|---|---|---|
| 0 | B | 0 | A + B |
| 1 | B′ | 1 | A + B′ + 1 ＝ A − B |
溢位（overflow）是答案超出能表示的範圍。5 + 3 ＝ 8，但是 4 位元有號數最大只到 7，加法器算出 1000，讀起來是 −8。判斷規則：進入最高位的進位和離開最高位的進位不同，就是溢位，V = C3 ⊕ C4。
注意 V 和 Cout 不是同一件事。Cout 是無號數的進位；同一組位元當有號數看時，要看 V。電路本身不知道你把位元當成哪一種，兩個訊號都給，由程式決定看哪一個。
逐位元看減法怎麼算
這段程式照著電路一位一位算。注意 sub 同時用在兩個地方：XOR 反相，以及一開始的進位。最後一組 −8 − 1 算出來是 7，V＝1，看看為什麼。
ALU：同時算好，再選一個
CPU 不只做加法，還要做 AND、OR 這類邏輯運算。負責這些運算的電路叫算術邏輯單元（arithmetic logic unit，ALU）。
作法出奇地直接：每一種運算都一直在算，最後用多工器選一個當輸出。 1 位元的 ALU 就是一個全加器、一個 AND、一個 OR，再加一顆 4 選 1：
| S1 | S0 | 運算 | Y |
|---|---|---|---|
| 0 | 0 | AND | A·B |
| 0 | 1 | OR | A + B |
| 1 | 0 | 加 | A ⊕ B ⊕ Cin |
| 1 | 1 | 減 | A ⊕ B′ ⊕ Cin |
多工器的選擇線，就是 CPU 指令告訴 ALU「這次做什麼」的地方。加與減共用全加器：讓 XOR 看 S0，S0＝0 時 B 原樣通過，S0＝1 時 B 反相。
代價是什麼？ 沒被選到的運算也在消耗電力，輸出也要等多工器多一層延遲。換來的是控制很單純：指令解碼完，只要改選擇線。多接幾個 1 位元 ALU，把進位串起來，就是 8 位元、64 位元的 ALU。
確認一下
全加器的輸入是 A＝1、B＝0、Cin＝1，輸出是？
4 位元二補數的 1110 代表多少？
4 位元有號數算 7 + 1，加法器輸出什麼，V 是多少？
用同一個 4 位元加法器算 3 − 5，Cout 與 V 應該怎麼解讀？
如果把 XOR 控制的 SUB 只接到各位元的 XOR，忘了接最低位的 Cin，5 − 3 會算出多少？
重點整理
- 半加器：
S = A ⊕ B、C = A·B。全加器再把進位加進來，共 5 個閘。 - 全加器串起來就是漣波進位加法器，進位一位一位往上傳。
- 二補數的負數是全部反相再加 1，所以減法就是
A + B′ + 1：用 XOR 做可控制的反相，多的 1 從最低位 Cin 進去。 - 有號數溢位看
V = C3 ⊕ C4，和無號數的 Cout 是不同的訊號。 - ALU 同時算好每一種運算，用多工器選一個輸出；選擇線就是指令控制它的地方。
到目前為止，我們都假設輸出立刻算好。其實不是：FA3 要等 FA0 的進位傳過來。下一課量量看要等多久，以及它怎麼決定時脈能跑多快。