移位相加乘法

移位相加乘法就是你學過的十進位直式乘法，因為二進位只有 0 和 1 兩個數字而變得極為簡單。要乘以一個十進位數字，你得會九九乘法表；要乘以一個二進位數字，你頂多只是乘以 0 或乘以 1。所以每一步只是：看乘數的一個位元——如果是 1，就把被乘數的一份移位副本加進累計總和；如果是 0，就什麼都不加。把位置往左移一位，重複。完全不需要乘法表。

走一遍 0b101（5）乘 0b011（3）。乘數（5）的第 0 位是 1，所以把被乘數 3 移 0 位後加入：總和 3。第 1 位是 0，什麼都不加；總和維持 3。第 2 位是 1，所以把 3 左移 2 位（即 3 乘 4 = 12）加入：總和 3 + 12 = 15，正確。在硬體中這變成一個迴圈，用一個暫存器累積乘積、一個加法器、一個移位器，對運算元的每個位元重複一次。一次 n 位元乘法約需 n 個相加並移位的步驟，所以它直觀正確但慢——大約是 n 個週期，而一次加法是一個。

這是衡量每個更快乘法器的基準。它誠實的弱點正是它是串列的：每一步都依賴前一步的累計總和，所以一次 64 位元乘法若真的一次一個位元做，可能要花上數十個週期。兩個大想法攻擊這點：Booth 演算法減少相加步驟的數目（並乾淨地處理有號數），而陣列或 Wallace 樹乘法器把所有部分積的加法以平行硬體一次做完、而非在迴圈中做，以面積換速度。