整数乘法的底层实现与溢出判断

是什么

• 定义：计算机底层没有单独的“乘法计算规则”，乘法是通过加法器（ALU）和移位器配合完成的。$n$ 位数相乘，硬件内部会产生 $2n$ 位的完整乘积，但在 C 语言赋值时会被==截断为低 $n$ 位==。

• 大白话：CPU 算乘法跟小学生列竖式一模一样，碰见 1 就把被乘数抄下来（加法），每算下一位就往左错一位（移位）。最后算出来的结果很长，但如果只能存进原来的坑位里，就只能把前面多出来的砍掉，砍掉的部分如果带有有效数值，那就是“溢出”了。

核心内容

1. 乘法的三种实现效率（从慢到快）

• 纯软件实现（最慢）：指令系统里没有乘法指令，全靠手写加法指令、移位指令和跳转指令拼凑出循环，每条指令都要取指、译码。

• 带硬件支持的指令实现：有专门的乘法指令，依靠微程序控制 ALU 和移位器自动循环完成。

• 阵列乘法器（最快）：纯组合逻辑电路（硬件铺在板子上直接连通），不需要时钟周期循环，信号一过结果就出来了。

2. 乘法溢出的核心逻辑（重点）

$n$ 位整数相乘，若保存为 $2n$ 位，绝对不会溢出。所有的“溢出”只发生在将 $2n$ 位的乘积强行截断保留低 $n$ 位时。

• 无符号乘法溢出判断：看 $2n$ 位乘积的高 $n$ 位。如果高 $n$ 位不全为 0，说明装不下了，溢出。

• 有符号乘法溢出判断：最直观的方法是看截断后的符号位是否发生异常变异（例如正数乘正数，截断后的最高位变成了 1）。

例题

• 题目：已知 32 位计算机，$x=2^{31}-1,y=2$。有符号整数乘法指令和无符号整数乘法指令得到的 $x\times y$ 的 64 位乘积分别是什么（十六进制）？此时 umul(x, y)（无符号）和 imul(x, y)（有符号）的返回结果是否溢出？如何用 64 位乘积判断无符号乘法的溢出？

• 分析（第四问详细推导）：

  1. 先算乘积：$x=2^{31}-1$ 是 32 位有符号数能表示的最大正数，十六进制为 7FFFFFFFH。

  2. ==移位等效==：$x\times y$ 就是乘 2，在底层等价于向左移 1 位，最低位补 0。7FFFFFFFH 左移 1 位变成 FFFFFFFEH。它的十进制真值是 $2^{32}-2$。

  3. 64位扩展：因为 $x$ 和 $y$ 都是正数，两正数相乘结果必为正。向高位扩展到 64 位时，直接全部补 0。

  4. 看返回值截断：C 语言函数返回类型都是 32 位，所以只保留低 32 位的 FFFFFFFEH。

     • 无符号类型 32 位范围是 $[0,2^{32}-1]$。我们算出来是 $2^{32}-2$，没超范围。

     • 有符号类型截断后，看到 FFFFFFFEH 最高位（最左边的位）是 1，这意味着两个正数相乘居然算出了个“负数”！发生正溢出。

• 答案：

  • 有符号 64 位乘积：00000000FFFFFFFEH

  • 无符号 64 位乘积：00000000FFFFFFFEH

  • umul()（无符号）：返回结果不溢出。（因为低 32 位足以表示结果 $2^{32}-2$）。

  • imul()（有符号）：返回结果发生溢出。（正数乘正数结果变成了负数 FFFFFFFEH）。

  • 无符号溢出判断方法：当 64 位乘积的高 32 位不全为 0 时，仅取低 32 位作为结果即发生溢出。

⚠️ 易错点

Warning

• 最容易搞错的点：以为 64 位的完整乘积会溢出 $\to$ 在底层的中间过程里，$n$ 位乘以 $n$ 位，给它 $2n$ 位的寄存器去存，是永远装得下、绝对不可能溢出的。溢出特指最终存回 $n$ 位变量时发生截断。

• 正数扩展的肌肉记忆错误 $\to$ 看到“有符号乘法”四个字，很多同学下意识觉得扩展到 64 位时要考虑补 1。本题 $x$ 的十六进制虽然带了一堆 F，但它的最高位（第31位）是 0（7 展开是 0111），它是正数！正数向高位扩展永远只补 0。