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选了后者，而今天的芯片设计师正在两头下注。