為什麼乘法比加法難
到這裡為止，算術邏輯單元已經能一次把一對 n 位數做加法與減法，你甚至已經看過進位預看加法器如何讓進位一口氣衝過所有欄位。加法是對 n 個欄位做一趟二進位加法的掃描。乘法不是這樣一趟掃描——它是一疊這樣的掃描。兩個 n 位數相乘，結果最寬可達 2n 位，而課本上的方法會用 n 個分開的加法把它疊出來。
回想你在十進位下手算乘法的方式：對乘數的每一位，你寫下被乘數的一個位移複本，再把整疊加起來。二進位讓其中每一步都幾乎不費力，因為乘數的每一位不是 0 就是 1。所以每個部分積要嘛是被乘數位移到定位，要嘛什麼都不是。難的部分不再是「我該寫下什麼」——而是「我該怎麼把這些列快速加起來」，而正是這個問題，把慢的乘法器和快的乘法器區分開來。
位移相加：一次一列、耐心十足的機器
最小、最便宜的乘法器會把同一個加法器反覆重用。這就是位移相加乘法，它其實就是把手算法跑在一個循序電路上。保留一個累加的積暫存器（一開始為零），從最低位那端開始，一次一位地走過乘數。每一步你看當前的乘數位：如果是 1，就把被乘數加進積的高半部；如果是 0，就什麼都不加。接著把全部向右移一位，讓下一位對齊，如此重複 n 次。
Multiply 5 (0101) by 6 (0110), 4-bit, shift-and-add bit multiplier bit action partial sum (8-bit) --- -------------- ------------ ------------------- b0 0 add 0 0000 0000 b1 1 add 5<<1 0000 1010 (= 10) b2 1 add 5<<2 0001 1110 (= 30) b3 0 add 0 0001 1110 (= 30) result = 30 (5 x 6, correct)
它管用，而且很小——一個加法器、幾個位移暫存器、一個小小的控制狀態機在數步驟。但注意它的代價：對 n 位的運算元，它大約要花 n 個時脈週期，因為它對每個乘數位依序做一次加法。用這種方式做一次 64 位乘法就是幾十個週期。這正是你在這條學習階梯上一再遇到的取捨——便宜的硬體換來緩慢的運算。要更快，我們要嘛做更少次加法，要嘛把它們並行做，而這兩個想法各有一個經典的答案。
Booth 演算法：把一串 1 化成一次減法
這裡有個美妙的算術洞見。乘數裡一串連續的 1，像 0111 1000，代表一串你寧可不要一個一個做的加法。但那一塊 1 等於一個大的 2 的冪次減去一個小的——0111 1000 就是 128 減 8——所以你不必做七次加法，只要在這串的頂端做一次加法、在底端做一次減法就好。Booth 演算法正是把這個技巧系統化，而且額外的好處是：它能直接處理有號的二補數運算元，對負數不需要任何特例。
在機制上，Booth 掃描乘數時，會同時看每一位以及它正下方的那一位（想像底部多掛了一個 0）。往上讀時，1 轉 0 標示一串的開始，觸發一次被乘數的減法；0 轉 1 標示結束，觸發一次加法；在一串相同位元的內部，你只做位移。誠實的告誡：Booth 在有長串 1 的運算元上大放異彩，但對 0101... 這種交替的樣式，它實際上可能比單純的位移相加做更多次運算。這就是為什麼真實晶片用一種精煉過的「改良式 Booth」，一次看兩個位元，保證不論位元樣式如何，都用 n/2 個步驟處理完乘數。
陣列與樹狀乘法器：花邏輯閘、買速度
循序乘法器把同一個加法器跨 n 個週期重用。相反的極端則是一口氣產生所有部分積，再用一整片加法器森林把它們加起來，在固定且短的延遲內完成。陣列乘法器鋪出一個 n 乘 n 的 AND 閘格網（每個算出一個部分積位元），餵進一片全加器網——一塊美麗、規則的矽方塊，產生答案的時間大約就是進位橫越並向下漣漪流過整個陣列所需的時間。它很快，但它的延遲仍隨 n 成長，而且很吃面積。
聰明的下一步是 Wallace 樹（以及它的表親 Dadda 樹）。它不把部分積排成一長排相加，而是用樹的方式把它們壓下來，用進位保留加法器把三列加成兩列、過程中完全不傳遞進位。因為一棵樹的高度只隨列數的對數成長，部分積會在約 log-n 層內塌縮，而不是 n 層。只有最後一步——把最終的兩列變成一個數——才需要一個真正會傳遞進位的加法器，而這正是快速的進位預看加法器發揮價值的地方。
注意這三種設計——循序、陣列、樹——共有的樣式。它們算出同一個積；差別只在於它們投入多少硬體、以及多快完成。這就是架構師反覆使用的那根槓桿：花面積與功率去縮短關鍵路徑，或省下硬體而用週期數來付帳。手機的低功耗核心也許偏好一個精簡的循序乘法器；伺服器的數值運算單元則樂於花上百萬個電晶體在一棵樹上，好在單一個管線階段內完成乘法。
除法：算術邏輯單元裡那個慢吞吞的孩子
如果說乘法是一疊加法，那除法更糟，而且背後有個深刻的原因。乘法可以事先猜出每一個部分積——每個乘數位都各自獨立地說「加上這個位移複本，或不加」。除法做不到。每一步你都得問「除數塞不塞得進剩下的部分？」來決定下一個商位，而在你做完前一次減法之前，你無法回答這個問題。這些步驟是環環相扣的：每一步都取決於前一步的結果，所以沒有像乘法樹那樣的並行捷徑。
基本硬體照搬長除法：把部分餘數左移，試著減去除數，若結果非負就留下它並記下一個為 1 的商位，否則還原舊餘數並記下 0。這種「還原式」除法對每個商位做一次試減——同樣是約 n 個依序、相依的步驟。一種叫非還原式除法的精煉做法避開了浪費的還原，高階晶片則用 SRT 除法（以 Sweeney、Robertson、Tocher 命名）靠一張小查找表，每一步產生好幾個商位。但即使是 SRT，本質上仍是迭代的。
讓乘法器與除法器上工
退一步看，整套算術工具就排好了。加法與減法靠二補數重用同一個加法器；快速加法器拿邏輯閘換更短的進位；乘法器是一疊有結構的加法器，你可以打造成便宜又慢、或大又快；除法則是那個頑固地循序、能避就避的傢伙。這些就是算術邏輯單元向處理器執行的每一條算術指令所暴露出的整數運算。
- 需要便宜的乘法器？用位移相加把一個加法器重用 n 個週期——面積小，結果慢。
- 想要速度，又想乾淨地處理有號運算元？採用 Booth（實務上是改良式 Booth）來把步驟減半並吸收掉符號。
- 想在大約一個管線階段內完成乘法？把邏輯閘花在陣列或 Wallace 樹乘法器上，最後用一次傳遞進位的加法收尾。
- 碰到除法？預期會有許多依序的週期——能換的地方，就用乘以倒數或位移來取代它。
這一切都還活在整數的世界裡，那裡每個值都精確，固定的位數要嘛裝得下答案、要嘛溢位。下一篇將離開那個舒適的世界，轉向小數以及極大或極小的數：一個浮點數單元如何對齊指數、對有效數字運算、正規化並捨入——以及當一個有限的字只能逼近實數時，隨之而來的那些誠實的意外。