移位加乘法：计算的算法引擎

乘法是算术的四大基本支柱之一，我们学习时将其理解为重复的加法。虽然这个概念足够简单，但对于每秒需要处理数十亿次操作的计算机来说，这种方法慢得令人无法接受。那么，数字系统是如何实现快如闪电的乘法呢？答案不在于蛮力，而在于一种优雅的算法之舞——移位和加法，这正是处理器的母语。

本文将深入探讨计算算术的核心，揭示复杂的乘法如何被分解为这些原始、高速的操作。第一章​​原理与机制​​将揭示二进制左移的基础魔力，探索硬件乘法器的自动化机制，并研究像布斯（Booth）算法这样用于高效处理有符号数的复杂解决方案。我们将看到从补码到规范有符号数位（CSD）的数据表示法如何与算法效率内在关联。随后，关于​​应用与跨学科联系​​的章节将拓宽我们的视野，展示这一单一原理如何驱动从硬件数据转换和数字信号处理到机器人导航和计算理论极限的方方面面。

乘法，其核心是一个我们熟悉的概念：它只是重复的加法。如果你想用 5 乘以 3，你只需将 5 自身相加三次。一台简单的计算机可以做到这一点，但会非常慢，特别是对于大数。想象一下两个 64 位数相乘——这可能需要很长很长时间。自然和优秀的工程都厌恶缓慢的过程。一定有更优雅的方法。的确如此。秘密就在于计算机所说的语言：二进制语言。

在我们日常的十进制系统中，乘以 10 是毫不费力的。我们只需在数字末尾加一个零。35 变成 350。我们没有执行任何真正的“乘法”；我们只是将数字向左移动。这是因为我们数字系统中的每个位置都代表 10 的幂。将一个数字向左移动一位，其值就乘以 10。

计算机做同样的事情，但是在二进制（以 2 为基）中。在二进制世界里，每个位置代表 2 的幂。那么，如果我们取一个二进制数，并将其所有位向左移动一个位置，在末尾加一个零，会发生什么呢？我们将其乘以 2。数字 5，即 $0101_2$，变成 $1010_2$，也就是 10。这种​​按位左移​​对于处理器来说是一种极其快速的操作，远快于通用的乘法。

这个简单的技巧是高速乘法的基础。我们可以将任何乘法分解为一系列的移位和加法。例如，我们如何将一个数 $N$ 乘以 3？由于 $3 = 2 + 1$，我们可以写成 $3 \times N = (2 \times N) + (1 \times N)$。在二进制操作中，这只是将数 $N$ 左移一位，然后与原始数 $N$ 相加。所以，$3 \times N = (N \ll 1) + N$。要用 8 位数计算 $3 \times (-25)$，我们首先找到 -25 的二进制​​补码​​形式，即 $11100111_2$。将其左移一位得到 $11001110_2$。加上原始数 $11100111_2$，得到最终结果 $10110101_2$，这确实是 -75。

这个原理具有极好的通用性。要乘以 10，我们可以使用恒等式 $10 = 8 + 2$。所以，$10 \times N = (8 \times N) + (2 \times N)$。由于 $8 = 2^3$ 和 $2 = 2^1$，这变成 $(N \ll 3) + (N \ll 1)$。只需两次移位和一次加法，就可以将任何二进制数乘以十。这比将 $N$ 自身相加十次要高效得多。

知道原理是一回事，制造一台机器来执行它是另一回事。我们如何自动化这个移位和加法的过程？想象一下处理器内部的一条小型装配线。我们需要几个寄存器，它们就像数字的临时存储仓。

我们称被乘的数为​​被乘数​​，并将其存储在寄存器 M 中。我们用来乘的数是​​乘数​​，存储在寄存器 Q 中。我们还需要一个寄存器来存放累积的结果，称为​​累加器​​ A，它从零开始。

该算法就像一台小小的时钟般运作的机器，对乘数 Q 的每一位都进行一次循环。在每个周期中，我们做两件事：

1. ​​检查​​：查看乘数的最低有效位 $Q_0$。如果该位是 1，意味着乘数中存在当前的 2 的幂，所以我们必须将被乘数 M 加到我们的累加器 A 中。如果该位是 0，我们什么也不做。
2. ​​移位​​：然后我们将合并的 A 和 Q 寄存器向右移动一位。这一步同时做了两件聪明的事情。首先，它有效地将 A 中的部分积除以二，为下一步对齐。其次，它将乘数的下一位带到 $Q_0$ 位置，准备在下一个周期中被检查。

我们对乘数的每一位都重复这个“检查并移位”的舞蹈。整个过程由一个控制器，即​​有限状态机（FSM）​​来管理，它在每个时钟滴答时发出正确的控制信号（A_load、AQ_shr 等），在 IDLE、ADD 和 SHIFT 等状态间转换，直到任务 DONE。在最后一个周期之后，完整的产品整齐地存放在合并的 A 和 Q 寄存器中。这个优雅的迭代过程将“移位和加法”的抽象思想变成了具体、物理的现实。

简单的移位加法对正数非常有效。但对于负数，计算机通常使用​​补码​​表示法来处理，情况又如何呢？天真地应用该算法会失败。我们需要一种更复杂的方法，一种能够无缝处理正数和负数的方法。

这就是 Andrew Donald Booth 的天才之处。​​布斯（Booth）算法​​是移位加技术的改进版本，对补码数同样有效。布斯算法不是一次只看乘数的一位，而是成对地看。

想象一下从右到左扫描乘数。简单的算法说“每当你看到一个 1，就加上被乘数”。布斯算法则更有辨别力。它寻找位模式中的变化。

• 当它看到一串 1 的开始（一个 0 后面跟着一个 1，即 01），它会说“啊哈！一个工作块开始了。” 它执行一次被乘数的​​加法​​。
• 当它看到一串 1 的结束（一个 1 后面跟着一个 0，即 10），它会说“这个工作块结束了。” 它执行一次被乘数的​​减法​​。
• 如果它没有看到变化（00 或 11），它只做移位，什么也不做。

为什么这个奇怪的加减法组合能行得通？二进制数中的一串 1，如 ...01110...，代表连续的 2 的幂之和：$2^3 + 2^2 + 2^1 = 14$。一个简洁的数学恒等式告诉我们，这也等于 $2^4 - 2^1 = 16 - 2 = 14$。布斯算法正是利用了这一点。它不是进行三次加法，而是执行一次加法和一次减法来等效实现。更准确地说，它在块的开始处（01 转换）加上，在块的结束处（10 转换）减去。

让我们看看它的实际操作。要将 $M = 0110_2$ (6) 乘以 $Q = 1001_2$ (-7)，算法在四个周期内进行。

1. ​​周期 1​​：它看到 Q 右端的位对 10（最低有效位 1 及其右侧一个隐含的 0）。规则：减去 M。然后移位。
2. ​​周期 2​​：下一对是 01。规则：加上 M。然后移位。
3. ​​周期 3​​：下一对是 00。规则：什么都不做。只移位。
4. ​​周期 4​​：最后一对是 10。规则：减去 M。然后移位。

操作序列是：减法、加法、移位、减法。这些步骤之后，就形成了正确的负数乘积 -42。同样的算法，无需任何更改，可以正确地将两个正数或任何其他组合相乘。这种统一性是其优雅的第一个标志。它不需要为符号设置特殊情况；补码表示法和巧妙的加/减/移位逻辑会自动处理一切。

布斯算法不仅能处理有符号数，还关乎效率。如果你需要乘以一个像 ...011111110... 这样有一长串 1 的数，标准算法将执行七次加法。而布斯算法只需执行一次减法和一次加法，中间有许多快速的“仅移位”周期。对于布斯算法来说，最佳情况是乘以零，这包括 n 次连续的仅移位操作，完全没有算术运算。

如果成对看位是好的，为什么不看更大的组呢？这就是​​基-4布斯（Radix-4 Booth's）算法​​背后的思想。通过检查重叠的三位组，算法可以决定不仅加或减 M，还可以加或减 2M。我们如何得到 2M？很简单！只需将 M 左移一位（M << 1）。这使得乘法器每个周期可以处理乘数的两位，大约将完成乘法所需的时间减半。

这种最小化操作的原理可以被进一步推广，特别是在那些需要不断乘以同一个固定数字的应用中，比如数字信号处理和 FIR 滤波器。在这里，我们可以使用​​规范有符号数位（CSD）​​表示法来表示固定系数。CSD 使用 $\{-1, 0, 1\}$ 这几个数字来表示一个数，并有一条特殊规则，即任何两个连续的数字都不能是非零的。对于任何给定的数，这种格式保证了非零数字的数量最少。

更少的非零数字意味着需要更少的加法或减法。例如，数字 377 是 $256 + 64 + 32 + 16 + 8 + 1$。一个简单的移位加法需要五次加法。通过将其重新编码为 CSD，我们发现 $377 = 512 - 128 - 8 + 1$，即 $2^9 - 2^7 - 2^3 + 2^0$。这只有四个非零项，意味着乘法可以用仅仅三次加/减操作和一些硬连线移位来实现——这在硬件和功耗上是显著的节省。

这些算法的力量和优雅与二进制数字系统密切相关。如果我们尝试使用不同的系统，这种魔力可能会消失。考虑​​二-十进制编码（BCD）​​，其中每个十进制数字由一个 4 位块表示。在 BCD 中，乘以 10 不是固定大小寄存器中的简单数字移位，乘以 2 也不是一次位移。它需要一次完整的 BCD 加法，这包括一个标准的二进制加法，然后是一个复杂的校正步骤（对任何超过 9 的半字节加 6）。在 BCD 中尝试计算 10N = 8N + 2N 会变成一连串笨拙的 BCD 加法，使其比纯二进制数的简单移位加法复杂得多。

这说明了一个深刻的观点：算法和数据表示是内在联系的。布斯算法是为补码量身定做的。如果你试图在带有​​反码​​数的旧系统上使用它，除非你添加一个最终的校正步骤，否则对于负乘数它会产生错误的答案。

这种算法和结构之间的紧密耦合也带来了非凡的鲁棒性。这个过程是如此机械化和可预测，以至于即使发生错误，其影响也可以被完美量化。想象一下，在一个 n 周期布斯乘法中，宇宙射线在第 k 个周期的移位操作前翻转了累加器 A 中的一个位。这个微小的错误不会导致混乱的失败。相反，它以一种完全有序的方式通过剩余的 n-k 次移位传播。最终结果的误差大小将精确地取决于错误发生的周期、翻转的位以及随后的移位操作，但其传播是完全可预测的。这不仅仅是一个算法；它是一台精密机械，其中每个部分、每个周期，甚至每个潜在的错误都遵循着优美的数学逻辑。

我们已经看到，宏大的乘法运算可以由卑微、几乎微不足道的计算机操作——移位和加法——构建起来。这似乎只是一个实现细节，是隐藏在硅芯片内的一个巧妙工程。但它远不止于此。这个单一的思想——复杂性可以由迭代的简单性构建而成——是一项基本原则，其影响波及无数科学和工程领域。这就像发现所有的音乐都可以由几个简单的音符和节奏生成一样。让我们来一次巡礼，看看“移位和加法”这个简单的节奏能带我们走多远。

我们发现移位加原理最直接的应用是在计算机算术逻辑单元（ALU）的核心。它不仅仅是关于两个二进制数相乘；它关乎翻译这一基本任务。人类用十进制（基数为10）思考，而计算机说二进制（基数为2）。为了让计算机显示一个数字给我们看，它必须将其内部的二进制表示转换为一种称为二-十进制编码（BCD）的格式，其中每个十进制数字都作为独立的 4 位组存储。

这种转换是如何完成的？最优雅的方法之一是一种被亲切地称为“倍加-加三”（double dabble）的算法，这是移位加思想的纯粹体现。想象你有一个 8 位二进制数。你还有三个用于 BCD 百、十、个位数的空槽。这个过程是一个八步的舞蹈。在每一步中，你将整个二进制数向左移动一个位置。但在你这样做之前，你要检查一下 BCD 数字。如果任何数字的值大于或等于 5，你就给它加 3。为什么？因为即将到来的左移相当于乘以 2。如果一个 BCD 数字是 5，移位会产生 10（二进制为 1010），这是一个无效的 BCD 数字。但如果你先加 3，5 就变成了 8。然后当你移动 8 时，它变成了 16（在 BCD 逻辑中是 1_0000），正确地将 1 进位到下一个十进制位。这是一个优美的、局部的校正规则，当重复执行时，会产生全局完美的翻译——所有这些都只用到了移位和简单的加法。

从 BCD 回到纯二进制的逆向过程，提供了移位加乘法更直接的应用。一个像 d₂d₁d₀ 这样的三位 BCD 数的数学值是 (d₂ × 10 + d₁) × 10 + d₀。数字电路可以迭代地实现这一点。它从值 d₂ 开始，乘以 10，加上 d₁，将结果乘以 10，最后加上 d₀。那么硬件是如何执行那个关键的“乘以 10”步骤的呢？正如 $x \times 10 = x \times 8 + x \times 2$。在二进制中，这是通过取数 x，将其左移三位（x << 3），再左移一位（x << 1），然后将两个结果相加来实现的。这个单一的应用揭示了整个故事：一个高层次的数学公式（用于多项式求值的霍纳法）直接转化为一系列最原始的可用硬件操作。

移位加的力量远远超出了精确整数算术的范畴。在数字信号处理（DSP）和科学计算的世界里，我们不断地处理实数的近似值。在这里，目标不仅是得到正确的答案，还要高效地得到它。

在设计数字滤波器——选择性地修改信号中频率的电路，就像你音乐应用中的均衡器——时，我们需要将输入信号乘以一组预定义的系数。通用乘法器在芯片面积、功耗和速度方面成本高昂。解决方案是创建“无乘法器”设计。我们可以将每个滤波器系数表示为少数几个 2 的幂的和与差，而不是一个单一的数。例如，乘以 0.875 与乘以 1 - 1/8 相同。这可以实现为 x - (x >> 3)，即一次减法和一次移位。规范有符号数位（CSD）表示法是一种系统化的方法，可以为任何数找到最有效的这种分解，从而最小化所需的加法和减法次数。这项技术使工程师能够构建出极其快速和高效的 DSP 芯片，这些芯片被硬连线以执行特定任务。

这种低层次的技巧具有高层次的后果。当设计一个滤波器以满足特定规格（例如，分离两个非常接近的频率）时，工程师面临着在不同滤波器架构之间的选择，如有限脉冲响应（FIR）和无限脉冲响应（IIR）。IIR 滤波器通常可以用少得多的内部计算来满足尖锐的规格，使它们看起来更有效。问题在于，它们的内部反馈使其对系数中的微小误差极其敏感。然而，通过使用 CSD 以少数几次移位和加法来实现这些敏感系数，并通过将滤波器精心构造为简单部分的级联，我们可以两全其美：通过无乘法器技术使 IIR 设计的效率变得实用和鲁棒。

但这里有一个微妙而深刻的教训。用一系列移位和加法代替理想的乘法并不总是一个简单的替换。考虑一个带有内部反馈的 IIR 滤波器。在一个理想化的设计中，我们执行一次乘法然后对最终结果进行四舍五入。在移位加实现中，我们可能会倾向于在每次中间加法后对结果进行四舍五入，以防止数字变得过大。事实证明，这会产生巨大的差异。每个四舍五入步骤都会向系统中注入一点微小的噪声或“误差能量”。在反馈回路中，这种能量可以累积，导致滤波器即使在没有输入信号的情况下也会产生微小、持续的振荡——一个“极限环”。这是机器中的幽灵，源于我们计算的结构本身。这告诉我们，如何计算与计算什么同样重要。在我们移位加序列中何时何地进行四舍五入这个看似无害的选择，可以从根本上改变系统的行为。

移位加思想的影响并不仅限于一维信号；它为在几何世界中导航提供了强大的引擎。

该领域最美的算法之一是 CORDIC（坐标旋转数字计算机）。假设你想计算一个角度的正弦和余弦——这是图形学、导航和物理模拟中的一项基本任务。CORDIC 算法只用移位和加法就完成了这项工作。关键的洞见是，任何旋转都可以分解为一系列更小的、特殊的微旋转。这些特殊旋转的角度的正切值是 2 的幂（例如 $\arctan(1)$、$\arctan(0.5)$、$\arctan(0.25)$ 等）。通过对向量的坐标进行简单的移位加操作，就可以计算出这样一个角度的旋转。通过应用一系列这样的微旋转，我们可以将一个起始向量旋转到任何期望的角度，而向量的最终坐标就给出了我们的余弦和正弦。这是一个惊人的演示，说明了复杂的几何变换如何能从最简单的算术步骤构建而成。

这种高效计算的原则在机器人学中找到了归宿。想象一个移动机器人在一个有障碍物的房间里导航。一个常见的策略是定义一个“人工势场”，这是一个数学景观，其中障碍是高山，目标是低谷。机器人通过计算“下坡”方向——即该场的负梯度——来决定移动方向。如果势场由多项式描述，这就要求机器人实时评估这些多项式及其导数。最有效的方法是一种称为霍纳法（Horner's method）的嵌套计算，它从根本上说是一系列乘加操作。在机器人的嵌入式处理器上，每一个时钟周期和每一比特的能量都至关重要，这些乘法通常是使用我们一直在探索的移位加技术来实现的。在这里，我们看到了整个指挥链：一个高层目标（导航）依赖于一个算法（梯度下降），该算法依赖于快速的数学求值（霍纳法），而这又依赖于移位加算术的基本效率。

最后，我们可以退后一步，从尽可能高的视角——计算理论本身——来看待移位加原理。在这里，我们不仅问如何构建一个电路，而且问从根本上说，什么是可以被高效计算的。

计算机科学家将问题分为不同的复杂度类。例如，$AC^i$ 类包含那些可以由多项式大小的电路解决的问题，其深度随着输入大小对数的 $i$ 次方增长。一个更小的 $i$ 意味着一个“更扁平”的电路和一个更快的并行算法。众所周知，乘法可以由非常高效的并行电路完成，使其处于像 $AC^0$ 或 $AC^1$ 这样的类中。

那么除法呢？除法似乎比乘法难得多。但复杂性理论中一个卓越的结果表明，难度并没有那么大。如果整数乘法在 $AC^i$ 中，那么可以证明整数除法在 $AC^{i+1}$ 中。它们之间的桥梁是一个经典的数值方法：牛顿法。要计算 $x/y$，我们可以先找到倒数 $1/y$。用于寻找倒数的牛顿-拉夫逊迭代非常简单：给定一个当前猜测值 $z_k$，下一个更好的猜测是 $z_{k+1} = z_k(2 - y z_k)$。注意，这个公式只涉及乘法和减法！此外，这个方法是二次收敛的，意味着正确数字的数量在每次迭代中都会翻倍。因此，要得到一个 $n$ 位精确的倒数，我们只需要大约 $\log n$ 次迭代。

整个除法过程因此被简化为对数数量级的乘法。在电路深度方面，这意味着除法的深度大约是 $(\log n) \times (\text{乘法深度})$。如果乘法在 $AC^i$ 中（深度为 $O(\log^i n)$），那么除法就落在 $AC^{i+1}$ 中（深度为 $O(\log^{i+1} n)$）。这是一个深刻而优美的联系。它表明，快速并行乘法算法的存在——这些算法建立在移位加的基本思想之上——直接促成了为看似困难得多的除法问题创建快速并行算法。我们在 ALU 硬件中首次听到的简单节奏，一直回响到抽象计算理论的最高层，塑造了我们对什么可以被高效计算的根本理解。