Appearance
题目
有实现 的两个 C 语言函数如下：
c
unsigned umul (unsigned x, unsigned y) { return x*y; }
int imul (int x, int y) { return x * y; }假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答下列问题。
(1) 若 M 的指令系统中没有乘法指令，但有加法、减法和移位等指令，则在 M 上也能实现上述两个函数中的乘法运算，为什么？
(2) 若 M 的指令系统中有乘法指令，则基于 ALU、移位器、寄存器以及相应控制逻辑实现乘法指令时，控制逻辑的作用是什么？
(3) 针对以下三种情况： ①没有乘法指令； ②有使用 ALU 和移位器实现的乘法指令； ③有使用阵列乘法器实现的乘法指令， 函数 umul() 在哪种情况下执行时间最长？哪种情况下执行的时间最短？说明理由。
(4) 位整数乘法指令可保存 位乘积，当仅取低 位作为乘积时，其结果可能会发生溢出。当 、、 时，带符号整数乘法指令和无符号整数乘法指令得到的 的 位乘积分别是什么（用十六进制表示）？此时函数 umul() 和 imul() 的返回结果是否溢出？对于无符号整数乘法运算，当仅取乘积的低位作为乘法结果时，如何用 位乘积进行溢出判断？
解析
本题考查 乘法的三种实现层次（软件 / 硬件多周期 / 硬件单周期） 与 n 位乘法的溢出判定。核心思想：
- 乘法本质是 "加 + 移位" 的反复，可在没有乘法指令的机器上用循环实现；
- 引入硬件乘法器 → 单条指令即可，多周期或一拍完成；
- n × n 位乘法产生 2n 位结果，截取低 n 位时可能溢出——有符号 / 无符号有不同的判定规则。
(1) 没有乘法指令也能实现乘法的原因 [2 分]
乘法可以分解为 "加 + 移位" 的迭代：把乘数逐位扫描，每遇到 1 就把被乘数左移相应位数后累加。如：
编译器把 x * y 翻译成一个循环：扫 y 的每一位，按位决定是否累加 x 的左移版本，扫完一轮即得乘积。这只需要 加 / 减 / 移位 / 比较 / 跳转 几种 ALU 已有的指令。
编者注（生僻术语）： Booth 算法是这一思路的优化版，能减少加 / 减次数；现代 CPU 内部的乘法器其实就是大量并行的"加 + 移位"网络（华莱士树 / 阵列乘法器）。
(2) 控制逻辑的作用 [2 分]
当机器有乘法指令但内部用 ALU + 移位器实现时，控制逻辑 负责：
- 控制循环次数——按字长 n 重复 n 步；
- 每步决定操作——根据当前扫到的乘数位是 0 还是 1，控制 ALU 是否做"加"，控制移位器做左 / 右移；
- 管理状态——维护部分积、计数器、最终输出寄存器。
简言之，控制逻辑把"加 + 移位"的迭代过程编成一条状态机。
(3) 三种实现下 umul() 执行时间对比 [3 分]
| 情况 | 实现 | 单次乘法时钟周期数 | 综合时间 |
|---|---|---|---|
| ① 没有乘法指令 | 软件循环（多条指令） | 数十~上百周期 | 最长 |
| ② 有乘法指令，内部 ALU + 移位器 | 单条指令、多周期完成 | n ~ 2n 周期 | 中等 |
| ③ 有乘法指令，阵列乘法器 | 单条指令、单周期完成 | 1 周期 | 最短 |
理由：
- ① 每次乘法要执行 数十条指令，每条指令都要取指、译码、执行；时间随 n 线性增长且常数大；
- ② 一条乘法指令进入 CPU 后由专用控制电路在内部跑 n 次"加 + 移位"，避开了取指 / 译码开销，但仍需多周期；
- ③ 阵列乘法器把所有"加 + 移位"展开成 组合逻辑，结果在一个时钟周期内稳定下来——硬件最贵但最快。
(4) n=32, x=2³¹−1, y=2 的乘积与溢出判定 [4 分]
Step 1. 算 64 位乘积。
- 数值上 ；
- 64 位表示：高 32 位 = 0，低 32 位 = =
FFFF FFFEH； - 完整 64 位机器数 =
0000 0000 FFFF FFFEH。
带符号、无符号乘法指令算出的 2n 位乘积一致（都是位级运算）：
Step 2. 判断截断后是否溢出。
| 函数 | 类型 | 表示范围 | 取低 32 位 = FFFF FFFEH | 数值解读 | 是否溢出 |
|---|---|---|---|---|---|
| umul | unsigned | FFFF FFFEH | 4294967294 | 不溢出 | |
| imul | signed | FFFF FFFEH | 溢出（应为 4294967294，超出 int 范围） |
易错点： "机器位级结果一样"不代表"语义层结果一样"。相同的 32 位位串，按 unsigned 是 4294967294（合法），按 signed 是 −2（与真实数学结果差距巨大）→ 是否溢出取决于 解释规则与表示范围的匹配。
Step 3. 无符号乘法的溢出判定。
理由： 无符号 n 位最大值是 ；若乘积超出，必然在第 n 位（0 起算）或更高位上有 1，即高 n 位非全 0。
编者注（生僻术语）： 对应地，有符号 n 位乘法的溢出判定 是"高 n+1 位（即高 n 位 + 低 n 位的最高位）既不全为 0 也不全为 1 时溢出"——比无符号的判定更严格，因为要把符号扩展考虑进来。这也是 2019-45 第 5 问的内容。