組合的意思是沒有記憶
上一篇導覽中，我們用電晶體開關搭出邏輯閘、寫出真值表，並透過NAND 完備性證明了一個不起眼的閘就能表達任何布林函數。這給了我們原始的能力，卻沒有組織——一堆散亂的閘很難拿來思考。本篇把邏輯閘打包成三種每顆處理器都成千上萬地使用的可重用積木。整個家族共享一個定義性的特質：它們是組合的，意思是輸出只取決於此刻的輸入，對過去毫無記憶。
想像一台純邏輯的自動販賣機：投入相同的硬幣，你永遠立刻拿到相同的零食，不管你昨天買了什麼。那個「沒有昨天」正是組合邏輯與下一篇要講的時序邏輯之間的分界線，後者真的會記住。記憶的代價是時脈與回授；組合積木兩者都沒有。它們不過是一團邏輯閘，在訊號穿過的極短延遲之後，安定到一個由輸入鎖死的答案。
多工器：用邏輯閘做成的開關
最有用的組合積木是多工器（mux）——一個資料選擇器。它有好幾個資料輸入、幾個選擇輸入，以及一個輸出，它只做一件事：把被選中的那個輸入轉送到輸出。一支鐵路轉轍桿是最完美的圖像：許多軌道匯入，扳桿（選擇線）決定哪一條繼續走，其餘的都被忽略。一個 2 選 1 的多工器用一個選擇位元 S 在輸入 A 與 B 之間挑選：S 為 0 時輸出是 A，S 為 1 時是 B。在邏輯閘層次，這不過就是 out = (A AND NOT S) OR (B AND S)——這證明了「選擇」並不比幾個 AND 加一個 OR 更神秘。
多工器能乾淨俐落地擴展。一個 4 選 1 多工器需要 2 個選擇位元來數出 00、01、10、11，並在四個輸入中挑選；一般而言，k 條選擇線可在 2^k 個輸入中挑選，而更寬的 mux 不過是更多 AND 閘餵入一個大 OR。你也可以用三個 2 選 1 多工器排成一棵小樹來搭出一個 4 選 1 多工器——由較小的選擇組合出較大的選擇，正是先前那一階所承諾的那種層層堆疊。
為什麼要這麼在意一個開關？因為選擇正是運算的核心。稍後你會看到一個 mux 決定下一條指令來自程式計數器加一、還是來自分支目標；決定一個運算元是暫存器的值、還是一個立即數；決定要把好幾個結果中的哪一個寫回。你會發現，那些選擇線正是控制單元產出的控制訊號。一顆處理器，粗略地說，就是一大群由控制操縱的 mux。掌握這一塊積木，資料路徑就不再像魔法。
解碼器：把多工器翻過來
解碼器是多工器的鏡像。mux 把許多輸入收束成一個；解碼器則把一個小數字扇開成許多條線，只點亮其中一條。一個 n 對 2^n 的解碼器把 n 個輸入位元當成一個二進位數，並抬高單獨一條輸出線——也就是編號與輸入相符的那一條。3 個輸入就有 8 個輸出，餵入 101（也就是 5）會讓第 5 號輸出線變高，其餘七條保持低。它是一個 one-hot（獨熱）轉譯器：把一個緊湊的二進位碼，變成一排只有恰好一個開著的開關。
它在哪裡發揮價值？位址解碼。當處理器想要編號 5 的暫存器時，解碼器把那個 5 變成唯一一條致能線，喚醒那個暫存器、而不喚醒其他任何一個；同樣的想法可以從上百萬個記憶體字組中挑出一個。解碼器也是運算碼變成控制的方式：把操作碼餵進去，恰好一條「做這個操作」的線會變高。mux 與解碼器是一對搭檔——一個選輸入，一個選目的地——它們聯手就能把資料送到晶片上的任何地方。
全加器：教矽片做加法
現在輪到主角登場。機器是怎麼做加法的？正是你手算的方式，一欄一欄地加，某一欄滿了就進位。負責一欄的那一格就是全加器。它接收三個輸入位元——這一欄的兩個運算元位元，加上來自右邊那一欄的進位輸入——並產出兩個輸出：一個和位元（這一欄的結果數字）與一個進位輸出（被推向左、進入下一欄的位元）。這五個值全是單一位元，所以整個東西不過是一張小小的真值表，用幾個閘就能搭出來。
Full adder truth table (a, b, cin -> sum, cout) a b cin | sum cout 0 0 0 | 0 0 0 0 1 | 1 0 0 1 0 | 1 0 0 1 1 | 0 1 1 0 0 | 1 0 1 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 1 1 sum = a XOR b XOR cin cout = (a AND b) OR (cin AND (a XOR b)) <- carry if any two are 1
把這張表讀一遍，一個規律就跳出來。每當三個輸入中有奇數個是 1 時，和位元就是 1——這就是 XOR，也就是奇偶性。每當三個輸入中至少有兩個是 1 時，進位輸出就是 1——這就是多數決。所以一個全加器不過就是「和取奇偶性，進位取多數決」。這正是小學加法的邏輯：1 加 1 等於 0 進位 1，而 1 加 1 再加一個進位等於 1 進位 1。
把加法器疊起來：一次加一整個字組
一個全加器處理一欄。要把兩個 32 位元的數相加，就串起 32 個：把每個加法器的進位輸出接到下一個加法器的進位輸入，就和你在紙上加法時進位往左流動一模一樣。那條鏈就是漣波進位加法器，加一整個字組最簡單的方法。餵入兩個 32 位元運算元與一個 0 的進位輸入，32 個和位元就會從頂端漣漪般冒出來。
- 把 32 個全加器並排，從第 0 位元（最右）到第 31 位元（最左）。
- 給每一欄它的兩個運算元位元；做加法時把最開頭的進位輸入設為 0。
- 把每個進位輸出接到下一個加法器的進位輸入，讓進位像手算一樣向左漣波。
- 那 32 個和位元就是你的答案；最後的進位輸出代表發生了無號溢位。
接下來是優雅、並回扣到先前導覽的部分。因為我們用二的補數儲存負數，同一個加法器也能做減法。要算 A 減 B，就餵入 B 的逐位元 NOT，並把第一個進位輸入設為 1——這悄悄組成了 (NOT B) + 1，也就是恰好的負 B，於是加法器算的是 A + (負 B)。一塊積木，兩種運算，由單一條控制線驅動進位輸入與反相來選擇。這就是為什麼真實晶片不需要一個獨立的減法器；算術邏輯單元（ALU）重用同一個加法器。減法就是加法戴上了偽裝。
誠實的代價：進位必須漣波
漣波進位加法器是正確的，但它有實實在在的代價，假裝沒有只會誤導你。每一欄的進位輸出，要等到右邊那一欄的進位抵達之後才能算出。所以進位必須依序穿過全部 32 個加法器，一個閘延遲接著一個閘延遲，最高位元才值得信任。這條鏈只能跟它最慢的路徑一樣快——而那條最長的路徑，也就是關鍵路徑，橫跨整個字組的寬度。一個漣波進位加法器的延遲隨位元數線性成長，對一台 64 位元機器來說慢得令人痛苦。
這個延遲之所以重要，是因為正如第一篇導覽所警告的，最長的組合路徑為時脈設下一道天花板。如果你的加法器是時脈必須等待的最慢東西，一個慢加法器就確確實實地拖慢了整顆處理器。所以在真實的 ALU 中，結構設計師不會將就於漣波進位。更快的設計——超前進位加法器、進位選擇加法器與平行前綴加法器——全都花費額外的閘來平行算出進位，而不是乾等它漣波，以矽片面積換取速度。我們在這裡不打開它們，但請記住這個一再出現的交易：你用更多硬體買來更短的關鍵路徑。