玻尔百科将两个数相乘，这个对人类来说微不足道的任务，在计算机的二进制世界中却提出了一个引人入胜的挑战。一个只理解“开”和“关”状态的机器，如何表示负数？它又如何将乘法规则转化为其可以执行的一系列操作？这就是有符号计算机算术的核心问题，其中，我们对数字的直观理解必须被编码成严格的比特模式。一种将有符号数当作无符号数来处理的幼稚方法，会迅速导致灾难性的错误，揭示了数学意图与硬件执行之间的根本鸿沟。
本文将踏上一段弥合这一鸿沟的旅程，探索为正确且高效地执行有符号乘法而开发的巧妙而富有洞察力的解决方案。在第一部分“原理与机制”中，我们将通过考察二进制补码表示法，理解为何简单的移位和无符号方法会失败，并逐步构建出稳健的解决方案，从而剖析其核心问题。我们将探索实用的基于校正的方法、Booth 算法的优雅顺序逻辑，以及 Baugh-Wooley 变换的卓越并行性。随后，“应用与跨学科联系”部分将展示这些基础算法并非仅仅是学术上的奇珍，而是驱动现代技术的引擎——从数字信号处理中的“无乘法器”设计和处理器算术逻辑单元（ALU）的架构，到对硬件安全的微妙而关键的影响。
想象你是一台计算机。你的世界不是由原子构成，而是由比特——数十亿个微小的开关，每个开关要么是开（1），要么是关（0）。你能够以难以想象的速度执行极其简单的操作。你可以相加，你可以将比特左移或右移。现在，有人让你将两个数相乘，比如说，-1 和 -1。在人类世界里，答案显然是 +1。但在你的比特世界里，“-1”究竟是什么样子？你又如何“乘以”它？
这就是计算机算术的核心挑战。我们凭直觉理解的数字必须被编码成比特模式，而我们学到的简单乘法规则必须被转化为处理器能够实际执行的一系列操作。通往正确且高效的有符号数[乘法算法](@article_id:331821)的旅程，是一个充满巧思和对数字本质深刻洞见的美妙故事。
首先，我们需要一种表示负数的约定。最常见且最优雅的系统称为二进制补码。在这个系统中，对于一个 比特的数，其最高有效位（MSB）并不像其他所有位那样代表一个正值；它代表一个负值，即 。例如，在一个 4 比特系统中，模式 1111 并非 。它代表的是 。
现在，让我们尝试使用一个为无符号数设计的简单硬件乘法器来计算 。一个无符号乘法器将 1111 视为数字 15。因此，当被要求将 1111 乘以 1111 时，它忠实地计算出 。在 8 位二进制中，225 是 11100001。这是计算机表示的 +1 吗？完全不是。+1 的 8 位二进制补码是 00000001。而结果 11100001，如果被解释为一个 8 位二进制补码数，实际上是 。
哪里出错了？无符号乘法器被符号位欺骗了。它把 1111 的最高有效位中的 '1' 当作一个正值（+8）来处理，而不是它在二进制补码中的真正含义（-8）。这一个误解在乘法过程中层层传递，最终产生了一个完全错误的答案。这揭示了一个基本事实：你不能像处理无符号数那样处理有符号数的乘法。比特的含义至关重要。
在我们构建一个全新的乘法器之前，或许有一些更简单的技巧？我们知道，在二进制中，将所有比特向左移动一个位置等同于乘以 2。这对处理器来说是一个极快的操作。我们能用它来处理有符号数吗？
让我们用一个 8 比特系统来试试。我们可以表示的数字范围是从 -128 到 +127。
假设我们有数字 -10，其二进制补码是 11110110。将其左移得到 11101100。这个新模式的值是 -20。完美运行！。
但我们不要高兴得太早。如果我们用 -96（10100000）来尝试呢？预期的答案是 -192。但一次左移产生了 01000000，这是 +64 的二进制补码表示。这不仅仅是错误；这是灾难性的错误——符号都变了！问题在于算术溢出。真实的结果 -192 超出了 8 比特所能表示的数字范围。比特模式从负数端“环绕”到了正数端。
这种脆弱性也延伸到更复杂的优化中。一个聪明的编译器可能会用一次移位和一次加法来代替乘以 3 的操作：。这是一种避免慢速乘法指令的巧妙方法。但这个恒等式何时会失效？恰恰是在真实的数学乘积 溢出 8 比特容器时失效。对于一个 8 比特系统，这个技巧只有在 介于 -42 和 +42 之间时才有效。在这个狭窄的范围之外，溢出会破坏结果。对于 256 个可能的输入值中的 171 个，这个“优化”会给出错误的答案。
移位是一个强大的工具，但它就像一辆跑车：速度快、优雅，却没有护栏。我们需要一种对所有数字都稳健的方法，而不仅仅是那些能保持在规则范围内的数字。
如果一个无符号乘法器给出错误的答案，或许我们可以“修复”它。如果我们用简单、错误的方式计算乘积，然后加上一个特定的“校正因子”使其正确，会怎么样？这是一个非常务实的方法，其背后的数学原理也惊人地优美。
让我们将一个 比特模式 的真实有符号值表示为 ，其无符号值表示为 。二进制补码的魔力在于，这两个值通过一个涉及符号位 的简单公式联系在一起：
对于另一个数 也是如此。正确的有符号乘积是 。让我们代入我们的公式：
仔细看第一项，。这正是我们简单的无符号乘法器所计算的！表达式的其余部分就是我们需要应用的校正因子。这为我们提供了一个清晰的有符号乘法器配方：使用一个快速的无符号乘法器，然后构建一些额外的逻辑来根据原始数字的符号位计算并应用校正。这种方法将问题分解为两个可管理的部分：一个我们已经知道如何解决的部分（无符号乘法）和一个新的、更小的问题（校正）。
这种方法在混合情况下甚至更有用，例如将一个有符号数乘以一个无符号数时。标准的“移位-加法”方法是可行的，但有一个关键的转折：当我们从有符号数生成部分积时，我们必须将它们符号扩展到最终乘积的完整宽度，以保留它们的负值。这种符号扩展，本质上是一种动态处理校正的方式。
校正方法很巧妙，但它仍然感觉像是一个补丁。有没有一种从头开始为有符号数设计的更根本的算法？有的，它被称为 Booth 算法。
标准的移位-加法乘法器逐一查看乘数的比特。如果一个比特是 '1'，它就加上被乘数；如果它是 '0'，则什么也不做。Booth 算法更聪明。它成对地查看比特。它的天才之处在于认识到一长串的 1，比如在数字 00111100 中，算术上等价于在该串的开头进行一次加法，并在末尾进行一次减法。例如，。在二进制中，001110 (14) 可以被认为是 010000 - 000010。
这种“重编码”方案将乘数从一串 0 和 1 转换成一串操作：（加被乘数）、（减被乘数）或 （无操作）。通过从右到左扫描乘数比特（我们称之为 ）并记录前一个看到的比特（），我们可以应用一个简单的规则：
00 或 11：处在一串零或一串一的中间。无操作。10：一串一的结束。我们执行一次减法（）。01：一串一的开始。我们执行一次加法（）。硬件只需要能够从三个选项中选择：、 和 。这就是基-2 Booth 算法的核心。让我们看一个在 5 比特系统中将 -5（被乘数 ）乘以 +6（乘数 ）的例子。
00。规则：无操作。将 A 和 Q 右移。 变为 00000， 变为 00011。10。规则：从 A 中减去 M。 变为 。右移。 变为 00010， 变为 10001。仅需两步，寄存器就持有了中间值，这些值最终将导向正确的乘积 -30。该算法通过其自身的结构优雅地处理了符号。对于某些数字，比如绝对值最大的负数 1000...0，Booth 算法非常高效。它将 10000000 重编码为 (-1)0000000，仅需一次减法，在这种情况下，这并不比标准算法更好，但也不差。然而，对于像 01010101 这样没有长串连续 1 的乘数，Booth 算法并没有性能优势。
Booth 算法很巧妙，而且通常很高效，但它本质上是顺序的。为了达到最高速度，我们希望一次性完成所有事情——并行地。这就是 Baugh-Wooley 算法的用武之地，它是数字设计的杰作。
它的目标是重新排列乘法过程，以便我们得到一个巨大的比特矩阵，所有这些比特都可以由一个简单的加法器树并行相加。正如我们所见，问题在于符号位会在部分积中引入负项，而在硬件中将正数和负数混合相加是复杂的。
Baugh-Wooley 的魔术是利用二进制补码的恒等式，将所有负的部分积转换为正的部分积，代价是增加一些固定的校正位。它重新排列了 的展开式，使得任何涉及符号位 或 的项都得到处理。例如，一个涉及 的部分积比特被替换为涉及其补码 的比特，外加一些常数。
结果是一个部分积矩阵，其中每个条目都是两个输入比特（或其补码）的简单逻辑与（AND），这些结果总是正的。这个矩阵可以被送入一个常规的无符号加法器结构，比如一个 Wallace 树。对于一个 和 的 乘法，该算法会生成一个由 16 个部分积比特组成的特定模式，其中一些比特是反相的，并加上一些硬连线的校正位。将所有这些比特相加，就得到了正确的乘积 +15。
但 Baugh-Wooley 的真正优雅之处在于它如何处理最终的求和。在将所有项重新排列为正值后，算法引入了一些固定的校正位。将这个完整的正位矩阵送入一个并行的加法器（如 Wallace 树）后，最终的求和步骤变得非常规整。通过巧妙的代数变换，原本复杂的带符号部分积求和问题，被转化为了一个标准的无符号并行加法，只需在最后阶段进行简单的、预先计算好的调整。这避免了在求和过程中处理负数的复杂性，实现了高速、高效的硬件设计。这正是物理学家和工程师们梦寐以求的那种深刻的简洁性。
到目前为止，我们只讨论了整数的乘法。但大多数来自科学和工程的现实世界数据——音频信号、传感器读数、股票价格——都涉及小数。处理器通过定点算术来处理这个问题。一个定点数实际上只是一个整数，它在一个固定的位置有一个假想的二进制小数点。例如，我们可能决定在我们的 16 位数中，前 4 位用于整数部分，后 12 位用于小数部分。其值就是整数值乘以一个缩放因子，比如 。
现在，当我们把两个这样的定点数相乘时会发生什么？设 和 ，其中 和 是整数，而 是小数位的数量。乘积是 。发生了两个关键的事情：
为了将这个结果存回原始的 位格式，我们必须丢弃一些比特。我们必须截断乘积，这带来了巨大的溢出风险。例如，在一种所有数的绝对值都小于 1 的格式中（这在数字信号处理中很常见），将 -1 乘以 -1 得到的数学结果是 +1。但用于表示小于 1 的数的二进制补码格式通常无法精确表示 +1。结果会溢出，导致巨大的错误。
为了防止这种情况，工程师必须主动采取措施。他们执行缩放。在乘法之前，他们可能会将输入数字右移，从而有效地使它们变小。这创造了“裕量”，以便在计算乘积时不会溢出。当累加许多乘积时，比如在滤波器或点积计算中，这种缩放变得更加关键。即使每个单独的乘积都能容纳，它们的和也很容易溢出。设计者必须计算最坏情况下的和，并选择一个能保证最终结果保持在可表示范围内的缩放因子。这种对比特增长和动态范围的仔细管理是定点 DSP 设计的基本挑战，而这一切都建立在对二进制补码乘法原理的深刻理解之上。
在经历了二进制补码的复杂机制和 Booth 算法的优雅逻辑之后，人们可能会感到一种智力上的满足。但科学不仅仅是优美思想的集合；它是一个用以构建和理解世界的工具箱。这个特定的工具——有符号二进制乘法——在哪里找到了它的用武之地？答案是，无处不在。从你计算机的硅芯片核心，到跨越全球传输你声音的无形信号，我们讨论的这些原理并非抽象的奇珍异物。它们是驱动现代技术的无声、高速的引擎。
现在让我们来探索这个广阔的应用领域，看看这些基本概念如何绽放为解决现实世界工程挑战的方案，将数字逻辑与信号处理、数值方法乃至密码学等不同领域联系起来。
一个完整的、通用的乘法器是一块功能强大但成本高昂的硬件。它在硅芯片上消耗大量面积，耗费电力，并可能成为性能瓶颈。就像一位知道并非所有任务都需要大锤的能工巧匠一样，一个熟练的数字设计师也有一套更轻巧、更优雅的工具。其中许多工具都围绕着一个优美的想法：完全避免乘法。
最简单的技巧是乘以 2 的幂。要将一个数乘以 2，你只需将其所有比特向左移动一个位置。要乘以 4，就移动两个位置，以此类推。那么乘以一个负的 2 的幂，比如 -2 呢？这也并不困难。你可以执行左移得到 ，然后取结果的二进制补码得到 。或者，你也可以先求二进制补码得到 ，然后执行左移得到 。两条路径都能得到相同的答案，这展示了硬件设计者可以利用的 flexibilidad。这绝非纯粹的学术练习；编译器会自动执行这种优化，在可能的情况下用近乎瞬时的移位操作来代替昂贵的乘法指令。
但如果常数不是 2 的幂，比如 18，该怎么办？在这里，我们同样可以避免使用大锤。我们可以将常数分解为 2 的幂的和或差。例如，因为 ，所以乘法 变成了 。在硬件中，这转化为将输入 通过两个独立的移位器（一个左移 4 位，另一个左移 1 位），然后将结果相加。这种“移位-加法”方法为单一任务构建了一个高度专用、高效的电路。这项技术是数字信号处理（DSP）的命脉，在 DSP 中，数字滤波器需要不断地将信号与固定的系数相乘。
将这种理念推向极致，我们发现了宏伟的 CORDIC（坐标旋转数字计算机）算法。想象一下需要计算正弦和余弦等三角函数，或是在二维平面上旋转一个向量。这些操作在图形学、机器人学和通信中是基础。一种蛮力方法会涉及复杂的乘法。然而，CORDIC 仅使用加法、减法和移位就完成了这些壮举。它的工作原理是执行一系列精心选择的微小旋转，每次旋转都经过设计，使得三角函数项简化为 2 的幂，从而可以用简单的位移来实现。CORDIC 是算法天才的证明，它是一个绝佳的例子，说明了对算术和几何之间相互作用的更深层次理解，可以如何带来异常优雅和高效的硬件。
虽然“无乘法器”技术很强大，但通用处理器无法回避对一个真正的、全能的有符号乘法器的需求。这正是像 Booth 这样的算法脱颖而出的地方，它不仅是一种方法，更是一份直接的硅片蓝图。
Booth 算法的美妙之处在于它对正数和负数的一致处理，以及其减少所需操作数量的潜力。通过成对检查比特，它可以跳过长串的 1 或 0，用字符串两端的一次减法和一次加法来代替多次加法。为了进一步提升性能，设计者开发了更高基数的版本。例如，基-4 Booth 算法以三元组为单位检查比特，每个周期处理乘数的两位而不是一位。这有效地将所需周期数减半，以稍显复杂的控制逻辑为代价，极大地加快了计算速度。
当然，纸上的算法并非电路。要将其变为现实，必须设计一个控制器——一个指导数据流的有限状态机。这个控制器是乘法器的“大脑”。它按顺序经历一系列状态，在每个状态中，它检查状态标志（如乘数的比特）并向数据通路发出命令：“现在，执行加法，” “现在，执行移位，” “现在，将计数器减一。” 为 Booth 乘法器设计算法状态机（ASM）图是一项经典练习，它弥合了抽象算法与具体硬件之间的鸿沟，精心编排了计算乘积所需的精确信号之舞。
硬件设计师也是节俭与优雅的大师。假设你有一个完美的无符号乘法器。你必须为有符号数重新构建一个全新的吗？不一定。无符号乘法和有符号乘法之间存在着深刻的联系。有符号数 的乘积可以与其无符号解释的乘积相关联，其中有一个取决于 的符号位的校正因子。通过添加少量“校正逻辑”在需要时减去这个因子，一个现有的无符号阵列乘法器就可以被改造以正确处理有符号数。这是二进制算术统一性的一个美丽范例，其中一个结构可以通过巧妙的修改来完成另一个结构的工作。
到目前为止，我们的讨论一直局限于整数领域。但真实世界充满了分数和连续值——电压、压力、声波。虽然浮点表示是处理这个问题的一种方式，但它复杂且耗电。对于嵌入式系统和 DSP 中的许多应用，一种更有效的方法是定点算术。
在定点数中，二进制小数点并不在字尾，而是在中间某个固定的、隐含的位置。例如，一个 Q4.4 数有 4 位用于整数部分，4 位用于小数部分。这些数的乘法仍然依赖于相同的底层整数乘法硬件，但我们必须小心结果的含义。当我们把一个 Q4.4 数乘以一个像 4（即 ）这样的整数时，硬件中的操作仍然只是一个简单的 2 位左移。然而，这个移位操作将比特移过了隐含的二进制小数点，从而有效地改变了数的值，就像放大器增强信号一样。
当我们像工程师那样，用硬件描述语言（如 VHDL）实际实现这一点时，这个概念变得异常清晰。将两个 位数（带有 个小数位）相乘会产生一个 位的中间乘积。这个新数的小数部分有 位长。为了回到我们原来的带有 个小数位的格式，我们必须丢弃乘积的低 位。这等同于算术右移 个位置。用于从完整乘积中选择正确比特片段的 VHDL 代码，例如 P(I+2*F-1 DOWNTO F)，正是这种二进制小数点数学重对齐的直接体现。
这个充满真实世界信号的世界也带来了一个新的挑战：溢出。在标准的二进制补码算术中，如果我们将两个大的正数相加，结果超出了最大可表示值，它会“回绕”并变成一个大的负数。对于音频处理来说，这是灾难性的，会产生一个响亮的“爆音”或“咔哒”声。解决方案是饱和算术。结果不会回绕，而是被“钳位”到最接近的可表示值（最大正值或最小负值）。检测饱和需求的逻辑很巧妙，它检查在更宽的中间乘积中可用的真实结果，是否存在会被截断但与简单符号扩展不一致的比特。这确保了过载的音频信号会平滑地削波，就像模拟放大器那样，而不是产生刺耳的数字失真。
我们通常认为计算是一个纯粹的逻辑过程，是对 0 和 1 的抽象操纵。但每一个操作都发生在物理设备上，一个消耗能量来改变状态的晶体管。在这个物理现实中，一个迷人而危险的联系出现了：计算与安全之间的联系。
想象一下我们的 Booth 乘法器正在埋头进行计算。在每个周期中，它可能会执行一次加法、一次减法，或者什么都不做只进行移位。这些操作并非完全相同。加法器电路与减法器不同，它们可能消耗略有不同的电能。现在，想象一个对手正在监控一个加密芯片的电源，该芯片正在将一个秘密数字（密钥）与某些数据相乘。
通过逐周期测量功耗的细微波动，攻击者可以获得一条功耗轨迹。如果一个功耗峰值为 5 个单位的周期对应一次减法，而一个 3 个单位的峰值对应一次加法，攻击者就可以将功耗轨迹直接映射回算法执行的操作序列。由于 Booth 算法中的加减法序列直接由乘数的比特模式决定，攻击者可以逐位重建秘密密钥，而无需破解数学加密本身。
这就是侧信道攻击，它揭示了一个深刻的真理：我们从像 Booth 这样依赖数据的算法中获得的效率，可能会产生漏洞。使其快速的那个特性——根据输入数据跳过操作——将关于该数据的信息泄露到了物理世界中。这催生了整个硬件安全领域，现在设计师不仅要制造正确和快速的电路，还要使其“常数时间”——即设计成尽可能少地泄露信息。
于是，我们的旅程在它开始的地方结束，即简单的乘法运算。我们见证了它从一个教科书式的算法转变为一系列优雅的硬件解决方案，一个操纵真实世界信号的工具，以及出人意料地，一个潜在的安全漏洞。这是科学与工程精神的完美体现：对一个基本概念的深入探索，揭示了一个丰富、相互关联、具有惊人深度、美感和实际重要性的世界。