問題所在：一個必須慢慢爬的進位
在上一篇導覽裡，我們把二進位加法用一排一位元的全加器組起來，每個位元位置一個，串成一條鏈，讓每個加器的進位輸出餵進下一個加器的進位輸入。那條鏈就是漣波進位加法器，它漂亮地簡單，而且完全正確。但它有個會隨字組大小一起變大的毛病：最高位元在進位從最右邊那一位、一路穿過中間每一個加器、一次傳一棒地漣波過來之前，根本算不完。
想像一排人在傳水桶。第 0 號要先知道從自己右邊傳來什麼，才能決定要不要把水桶傳給第 1 號；第 31 號就只能卡著，等整排人依序動作。對一個 32 位元的漣波加法器，最壞情況會把大約 32 個進位傳遞延遲首尾相接地疊起來。那條由相依的閘串成的長鏈，就是這個加法器的關鍵路徑——訊號穿過電路可能走的最慢一條路，也正是它決定了整台機器能被打多快的時脈。
關鍵想法：預測進位，而不是等它
這裡有個能斬斷那條鏈的洞見。看一個單一位元位置，它的輸入位元是 a 和 b。早在任何進位抵達之前，這個位置就已經知道關於自己的兩件事。如果 a 和 b 都是 1，無論從右邊進來什麼，它都會送出一個進位——把這叫做產生（generate），寫成 g = a AND b。如果 a 和 b 恰好只有一個是 1，它就會把收到的任何進位原封不動地傳下去——把這叫做傳遞（propagate），寫成 p = a OR b。產生與傳遞只看本地的輸入，所以每一個位置都能在同一瞬間平行地算出它們。
現在，任何位元的進位輸入都可以寫出來，而不必等漣波。第 i 位的進位輸入為真，當且僅當第 i-1 位產生了進位，「或者」第 i-1 位是傳遞而且第 i-1 位的進位輸入為真——而你可以一直把後面那個子句代換下去，直到它觸底到最一開始的那個進位輸入。把式子乘開來，比方說第 4 位的進位輸入，就變成一條由各個 g、各個 p 與初始進位組成的扁平公式——一個寬寬的 AND-OR，無論第 4 位坐在這條線多下面，電路都只用固定的兩個閘延遲就能算出它。那條扁平、平行的公式，正是進位前瞻加法器（carry-lookahead adder）的核心。
Carry equations, written out flat (c0 = the incoming carry): g_i = a_i AND b_i # this bit GENERATES a carry on its own p_i = a_i OR b_i # this bit PROPAGATES an incoming carry c1 = g0 + p0.c0 c2 = g1 + p1.g0 + p1.p0.c0 c3 = g2 + p2.g1 + p2.p1.g0 + p2.p1.p0.c0 c4 = g3 + p3.g2 + p3.p2.g1 + p3.p2.p1.g0 + p3.p2.p1.p0.c0 ( '.' = AND, '+' = OR ) Every c_i is one AND-OR layer over the g's and p's -> ~2 gate delays, all carries ready at once instead of rippling one by one.
這筆交易：用閘與線換速度
天下沒有白吃的午餐。看看 c4 的公式，會發現它的項數比 c1 多；而 c32 的公式會大得嚇人，需要有幾十個輸入的 AND 閘，以及一整片把傳遞訊號散布到整個寬度的線林。漣波加法器付的是時間——許多串接在一起的小延遲。前瞻加法器付的是空間——許多同時運作的閘與線。這是所有硬體裡最基本的一筆交易：你幾乎總是能用更多的閘（面積、功耗、成本）去換更少的延遲，而進位前瞻加法器正是課本上的範例。
因為對 32 位元做單一扁平前瞻會需要寬到不可能的閘，真實的設計改採階層式。把 32 位元切成一組四位元。在每一組裡建一個小小的 4 位元前瞻，並讓每一組同時對外輸出一個群組產生與群組傳遞——這整塊四位元到底會不會產生進位，或者只是把進位直接傳穿過去？接著高一層的第二個前瞻單元，把每一個 4 位元群組當成一個胖胖的單一位元，用同樣的方法去算群組「之間」的進位。總延遲增長的速度像寬度的對數，而不是寬度本身——對 32 位元大約是寥寥幾個閘延遲，而不是 32 個。
一整個快速加法器家族
前瞻不是唯一的招數。進位選擇加法器（carry-select adder）採取一種妙在直白的做法：對較高的一塊位元，不要等著知道真正的進位輸入是什麼——乾脆把這段和平行算兩遍，一遍假設進位是 0，一遍假設進位是 1。等下方真正的進位送上來時，兩個答案都已經備妥；接著一個多工器只要單純挑出正確的那個預先算好的結果就行。這就是進位選擇加法器，在一塊位元上花掉雙倍的加器硬體，去藏起它原本得花在等待上的時間。先臆測，再挑選。
在最快的那一端，住著平行前綴加法器，它們把產生與傳遞訊號的組合排成一棵平衡的二元樹，讓全部 32 個進位在大約以 2 為底、32 的對數那麼深的層數裡解出來，也就是大約 5 層邏輯。這個家族裡不同的成員——Kogge-Stone、Brent-Kung 等等——在深度、線的數量與閘的扇出之間做出不同的取捨，而那正是晶片設計師會去轉的旋鈕。這些就是住在現代 ALU 速度關鍵核心裡的加法器。
真正該記住的是什麼
退一步看，這裡的教訓比加法器本身更大。這些設計裡的每一個，算出的都是和那個樸實的漣波加法器完全相同的和——一樣的輸入、一樣的輸出位元、一樣的溢位行為。它們的差別只在於有多快、有多大。這正是工程師每天的現實：正確性是地板，在它之上，你把面積、功耗與延遲互相權衡，去打中機器其餘部分所需要的目標。
- 對每一個位元位置一次算出產生 g = a AND b 與傳遞 p = a OR b——它們不需要進位，所以是瞬間且平行的。
- 把各個 g 與 p 餵進一個前瞻（或前綴樹），由扁平公式算出每一個進位，深度是對數而非線性的。
- 接著每一位的和不過就是 s = a XOR b XOR 進位輸入，一旦它的進位已知，就在本地瞬間算出。
- 依照你拿到的延遲預算與閘／功率預算去挑設計——漣波、進位選擇、前瞻或前綴——而不是依照哪個「最好」。
一句誠實的提醒：並沒有哪一個「最快的加法器」對每一塊晶片都對。一顆小小的低功耗微控制器，可能很樂意留著漣波加法器，因為它緩慢的時脈留下大把時間，而閘很珍貴；一顆高階 CPU 則願意為一棵很深的前綴樹付錢，因為加法器正正坐在它的關鍵路徑上。正確答案永遠相對於時脈目標、你挪得出的面積，以及你燒得起的功率——這也是整道階梯反覆出現的主題：讓常見情況變快，而且只在速度真的能替你換來東西的地方，才為它付錢。