1951年，安德鲁·唐纳德·布斯在实验室里盯着一堆电子管发呆。他刚算出两个二进制数的乘积，用了整整127个时钟周期。这个数字让他牙疼——按这个速度，一台计算机每秒只能做几百次乘法，连算个工资表都要卡半天。
70年后，你手机里的芯片每秒能执行数万亿次乘法。这个跨越的秘密，就藏在他当时随手写下的几行推导里。
二进制乘法的笨办法，有多笨？
先做个实验。打开计算器，输入 14 × 5。你眨眼间得到 70，但电脑看到的完全是另一幅画面：
14 变成 1110，5 变成 0101。然后它要这样算：把 1110 和 0000 做与运算，移位，再和 1110 做与运算，再移位，再和 0000……重复四次，最后把四个中间结果加起来。
传统方法的死穴在于：不管乘数里有多少个 0，你都得老老实实走完所有步骤。 乘数是 16 位？16 轮循环。32 位？32 轮。每个 0 都在浪费晶体管的寿命。
布斯当时的观察很毒：乘数里出现连续的 1 或连续的 0 时，其实可以"批量处理"。比如 0111（十进制的 7），传统算法要加三次；但他发现这等价于 1000 减 0001，一步到位。
布斯的减法 trick，把乘法变成加减移位
算法的核心是个状态机，只看当前位和右边那位：
00 或 11 → 什么都不做，直接移位。
01 → 被乘数加到累加器，然后移位。
10 → 被乘数从累加器减去，然后移位。
关键洞察在这里：连续的 1 会被自动转换成"高位加、低位减"的组合，跳过了中间所有无意义的加法步骤。乘数里 0 越多，省下的周期越多。最坏情况和传统方法一样，但平均能快 30% 到 50%。
1951 年的论文里，布斯用 11 个电子管实现了这个逻辑。今天 ARM 和 x86 的乘法指令单元里，它的变体仍在运行——只是被做成了纳米级的电路，一个时钟周期就能吞吐 64 位乘法。
从电子管到硅片：一个算法的 70 年漂流
布斯的原始设计有个毛病：处理有符号数（负数）时需要额外步骤。1960 年代，麦克索利（MacSorley）把它改成了"补码 Booth"，消除了这个麻烦。这是现在教科书里的标准版本。
1980 年代，流水线 CPU 兴起。工程师发现 Booth 编码特别适合并行化——你可以同时预判多位，把单周期乘法从科幻变成现实。1993 年英特尔的 Pentium，64 位浮点乘法就是 3 级 Booth 流水线。
2010 年后，移动端芯片对功耗锱铢必较。Booth 算法的变种被用来减少部分积（partial product）的数量，直接降低动态功耗。苹果 M1 的乘法单元里，4 位 Booth 编码把部分积从 16 个压到 9 个，省下的晶体管拿去堆神经网络加速器了。
一个冷知识：GPU 的矩阵乘法核心（Tensor Core）底层， still 能看到 Booth 编码的影子。 只是被包装在更激进的华莱士树（Wallace Tree）和进位保留加法器里，普通人再也认不出来。
为什么这个 70 岁的算法还没死？
数字电路的物理限制变了无数次，但二进制乘法的基本矛盾没变：你想用加法器阵列硬堆速度，面积和功耗就爆炸；你想省资源，就得在编码层面做聪明事。
Booth 算法恰好卡在甜蜜点上——实现简单（几十行 Verilog），效果稳定（平均提速 30%+），扩展性强（从 4 位到 1024 位都能用）。RISC-V 的乘法指令集里，它是指令精度的默认实现参考。
更隐蔽的优势在验证端。形式化验证工具喜欢 Booth 的规整结构，状态转移表写清楚，数学证明能自动跑完。这对车规芯片和航天级 CPU 是硬需求——乘法算错一位，刹车系统可能就判定你踩了油门。
2023 年，MIT 的研究团队试过用机器学习生成乘法电路，在特定数据集上比 Booth 快 12%。但泛化到随机输入就翻车，功耗曲线也难看。论文最后承认：「在通用场景下，Booth 的变体仍是帕累托最优解。」
布斯 1951 年的那几页手稿，现在存在伦敦科学博物馆。展签上写着「早期计算机算术优化」。路过的小孩不会多看一眼——他们手机里的芯片，正以每秒百亿次的频率，执行着这个老人想出来的减法 trick。
你上次注意到手机计算器有延迟，是什么时候？
热门跟贴