1950年Booth算法：CPU乘法比你想的省了47%運算量

你的CPU每秒執行幾十億次乘法，卻從沒告訴過你：它用的不是小學課本那套豎式。

1950年，英國數學家Andrew Donald Booth在倫敦大學伯貝克學院做晶體管計算機研究時，發現傳統二進制乘法有個反直覺的漏洞——算得越多，反而越慢。他設計了一套新規則，把連續重復的1變成減法+移位，讓硬件電路省掉近一半的加法操作。這套方法后來成了每臺計算機的標配，卻極少有人知道它的存在。

二進制乘法的"體力活"困境

先回憶一下人怎么算乘法。23×4，你其實算的是(20+3)×4=80+12，分解完逐位相乘再相加。二進制也一樣，只是更枯燥：1101×1011，要算四次1×1、1×0、1×1、1×1，然后錯位相加。

問題是，計算機的"錯位相加"不是紙上的斜線，是實打實的硬件加法器（加法運算電路）。每多一個1，就多一次加法。更麻煩的是負數——早期計算機用原碼表示，負號單獨存，乘法前要先判斷符號、取絕對值、算完再還原，一套流程下來，電路復雜度直接翻倍。

Booth的觀察很具體：二進制里連續出現多個1，比如1110，其實可以改寫為10000減0010。從加法視角看，三個1需要三次加法；換成減法+移位，只需要一次減法和幾次移位——而移位在硬件上幾乎是免費的，電線接錯位就行。

Booth算法的核心把戲：看相鄰兩位

算法的精髓藏在兩個相鄰比特的"組合狀態"里。Booth規定了一個編碼表：當前位是0、前一位也是0，什么都不做；當前位是1、前一位是0，加上被乘數；當前位是0、前一位是1，減去被乘數；兩個都是1，同樣什么都不做。

這個規則覆蓋了所有情況，卻巧妙地把連續1的串壓縮成"起點的加"和"終點的減"。

舉個例子：乘數二進制是01110（十進制14）。傳統算法遇到三個1，要做三次加法。Booth算法掃描時發現：從0變1的位置（左數第二位）執行加，從1變0的位置（右數第一位）執行減，中間連續的1全部跳過。結果變成一次加、一次減、若干移位——運算量從3次加法降到1次加1次減。

硬件實現上，這只需要一個加法器、一個減法器（或把減法轉成補碼加法）、一個能左右移位的寄存器。1950年代的晶體管貴如黃金，省一個加法器就是省一大筆錢。

補碼二進制的神助攻

Booth算法真正的爆發，要等到補碼（補碼表示法）成為整數標準之后。補碼的妙處在于：負數不需要額外符號位，正數和負數的加減法用同一套電路就能處理。

在補碼系統里，Booth算法可以直接處理帶符號乘法，不需要前置的符號判斷。乘數是正是負，編碼規則一視同仁——掃描相鄰位、決定加減、移位、繼續。這讓硬件設計極度簡潔，也解釋了為什么Intel 4004（1971年）之后的處理器都內置了Booth乘法器。

現代CPU的乘法指令（如x86的MUL/IMUL）底層仍是Booth的變體，只是做了并行化擴展。ARM的乘法單元、GPU的流處理器、甚至比特幣礦機的ASIC，都在用這套70年前的邏輯節省晶體管。

從論文到硅片的70年

Booth 1951年的原始論文《A signed binary multiplication technique》只有四頁，卻解決了當時計算機架構的核心瓶頸。他所在的伯貝克學院當時正在建造APEXC計算機，算法直接落地驗證。

有趣的是，Booth本人后來轉向神經網絡研究，1950年代就發表過用機械計算機模擬神經元的論文。他的乘法算法反而成了"一錘子買賣"——足夠好用，后續改進都是工程優化而非原理顛覆。

今天的處理器乘法器已經高度并行，能同時處理多個Booth編碼位（Radix-4、Radix-8版本），但核心思想沒變：把重復的加法換成更便宜的移位，用相鄰位的模式識別代替逐位硬算。

下次你寫代碼做整數乘法，編譯器生成的機器碼里，那條MUL指令的電路路徑上，Booth的編碼表仍在以納秒級的速度被查詢執行。一個1950年的數學技巧，就這樣藏在每一場計算的最底層——沒有啟動畫面，沒有版本號，甚至大多數計算機系學生直到體系結構課才會聽說它的名字。

如果讓你重新設計一套乘法算法，你會選擇優化延遲還是面積？Booth選了后者，而今天的芯片設計師正在兩頭下注。