ALU 如何做乘法 (无符号整数)

手算十进制和二进制乘法的过程

无论是十进制还是二进制，我们从小被训练的”竖式乘法”逻辑本质上是 “错位全加”。

以纯二进制无符号数乘法 1101 (被乘数，十进制 13) $\times$ 1011 (乘数，十进制 11) 为例，手算过程如下：

.
        1 1 0 1
      x 1 0 1 1
      ---------
        1 1 0 1  抄写被乘数
      1 1 0 1    被乘数左移 1 位
    0 0 0 0
+ 1 1 0 1        被乘数左移 3 位
---------------
1 0 0 0 1 1 1 1  (143)

错位相加的本质就是被乘数与乘数的每位位权的单独相乘再相加：

456 \times 789 = 456 \times (7 \times 1 0^{2} + 8 \times 1 0^{1} + 9 \times 1 0^{0})

1101 \times 1001 = 1101 \times (1 \times 2^{3} + 0 \times 2^{2} + 0 \times 2^{1} + 1 \times 2^{0})

最大问题：ACC 需要做成被乘数的 2 倍位宽

如果让计算机的 ALU 完全照搬人类这种”左移并相加”的逻辑，会带来硬件设计上的浪费。

假设我们正在进行现代计算机最常见的 32 位乘法（两个 int 类型的数相乘）：

乘数有 32 位，意味着 ALU 需要累加 32 次部分积。按照左移的逻辑，到了最后一次累加时（乘数的最高位），原本 32 位的被乘数已经在末尾补了 31 个 0。这使得被乘数在物理层面上被拉长到了 63 位。

这意味着计算机底层做加法时为了把这个膨胀到 64 位的被乘数加到 ACC 中，CPU 中必须在这个 ALU 中焊入一个 64 位宽的加法器和寄存器。执行 32 位数据的运算，要耗费双倍的成本。这种极度浪费硬件资源的设计，是工程学上绝对无法容忍的。

新的设计思路

方法是以时间换空间的乘法器设计，被乘数不动，部分积和城商寄存器 MQ 的内容整体右移位。

在这个新架构中，我们只需要固定位宽的加法器，并引入三个核心寄存器相互配合：

被乘数寄存器 (X)：固定位宽（例如 4 位或 32 位）。存放被乘数，内容不动。
乘数寄存器 (MQ)：存放乘数。它每次向右移位，把最低位”挤”出去给控制电路做判断。同时，它移位空出来的高位，用来接收乘积的低位。
累加器 (ACC) + 进位标志 (C)：初始清零。用来存放累加过程中的”高位部分积”。

运算过程（每个周期分两步）：

一看位加法：看 MQ 的最低位。如果是 1，ACC = ACC + X；如果是 0，ACC 不变（加 0）。
整体逻辑右移：将进位标志 C、累加器 ACC 和乘数寄存器 MQ 连成一个长长的整体，统统向逻辑右移 1 位。

四位乘法举例

现在重新推演一次 1101 $\times$ 1011 的计算过程。

硬件准备：固定 4 位加法器。
初始状态：X = 1101，C = 0，ACC = 0000，MQ = 1011。

轮数	执行动作	C	ACC	MQ	动作
初始	状态准备	0	`0000`	`1011`	盯住 MQ 最低位：1
第一轮	+ X (因 MQ 最低位=1)	0	`1101`	`1011`	ACC = 0000 + 1101 = 1101
	右移 1 位	0	`0110`	`1101`	C 的 0 进入 ACC 高位，ACC 最低位挤入 MQ 高位
第二轮	+ X (因 MQ 最低位=1)	1	`0011`	`1101`	ACC = 0110 + 1101 = 10011，产生进位 1
	右移 1 位	0	`1001`	`1110`	进位 1 填入 ACC 最高位，整体右移
第三轮	+ 0 (因 MQ 最低位=0)	0	`1001`	`1110`	ACC 原封不动
	右移 1 位	0	`0100`	`1111`	继续整体右移
第四轮	+ X (因 MQ 最低位=1)	1	`0001`	`1111`	ACC = 0100 + 1101 = 10001，产生进位 1
	右移 1 位	0	`1000`	`1111`	进位 1 填入 ACC 最高位，最后一次右移完成

经过 4 轮循环，运算结束。我们将最终的 ACC 和 MQ 拼接在一起，得到： 1000 1111

十进制转换验算：1000 $\times$ 1111 正好等于 128 + 8 + 4 + 2 + 1 = 143。与手算结果完全一致。

通过这种”右移累加”的机制，原本需要 8 位宽（甚至 64 位宽）加法器才能完成的乘法，被极其巧妙地压缩在了 4 位宽（或 32 位宽）的 ALU 中。

结果溢出

两个 $n$ 位的数字相乘，结果最大可能会膨胀到 $2 n$ 位。当 ALU 算完乘法的那一瞬间，它会用两个寄存器拼在一起来保存这个 $2 n$ 位的完整精确结果：

高位寄存器（ACC）：装载结果的高 $n$ 位。
低位寄存器（MQ）：装载结果的低 $n$ 位。

截断 (保留低 n 位)

既然硬件算得很准，为什么还会出错？问题出在高级编程语言的数据类型限制上。当我们用 C/C++ 这样的语言写代码时：

int a = 1000;  // 32 位
int b = 1000;  // 32 位
int c = a * b; // 注意：接收结果的 c 依然被限制为 32 位！

你规定了变量 c 只有 32 位（ $n$ 位），CPU 会直接把低位寄存器里的 $n$ 位数据塞给 c，然后把高位寄存器里的数据丢弃。

平时如果算的数字比较小（比如 $1000 \times 1000 = 1, 000, 000$ ），100 万在二进制里只需要 20 位就能存下。此时硬件算出的 64 位结果中，高 32 位全都是毫无意义的占位符 0。扔掉这些 0 对结果没有任何影响，保留下来的低 32 位依然是精确的 100 万。

但是当有效数据越界，真实的数学乘积超过了 32 位能容纳的极限（2^31-1 约 21 亿），有效数据就会溢出到高 32 位去。这时候再执行截断，就会出现整数溢出（Integer Overflow） 问题：

#include <iostream>
int main() {
    int a = 100000;  // 10 万
    int b = 100000;  // 10 万
    int c = a * b;   // 100 亿

    std::cout << "10 万 * 10 万 = " << c << std::endl; // 1410065408
    return 0;
}

代码的输出不是 100 亿，而是 1410065408。100 亿换算成二进制为 34 位。最顶上的那 2 位核心有效数据，被安全地存放在了硬件的高位寄存器里。然而，C++ 的 int 默认截断高位，只把剩下的低 32 位二进制强行翻译成十进制交给你，就得出了这个结果。

在底层的开发中，如果预判乘法的结果会非常大，必须在运算前将变量强制提升为 64 位类型（long long），强迫系统把高位寄存器里的数据也一并捞回来。