乘法

乘法运算常见有三类实现方式：

实现方式	基本思路
迭代式乘法器	复用同一个 ALU 和寄存器，每轮根据乘数位决定加、减或不操作，再移位。若一次ALU加法和一次移位各需要一个时钟周期，则对于$n$位乘法需要$2n$个时钟周期
阵列乘法器	用大量并行硬件同时生成并累加部分积，可在一个时钟周期内完成一次乘法运算。速度最快但硬件开销大。
移位-加减法	从算法层面把乘法转化为移位、加法、减法，硬件成本最低但速度最慢

下面介绍的即迭代式乘法器

无符号乘法

乘法过程可以用三个核心寄存器理解：

ACC 和 MQ 常连在一起看作一个双倍位宽寄存器：

ACC | MQ

乘法的核心动作是：

Note

若 ACC + X 产生进位，进位也要参与后续右移。

若两个 n bit 无符号整数相乘，完整乘积最多需要 2n bit 表示。

例如两个 8 bit 无符号整数：

$$
255 \times 255 = 65025
$$

这个结果需要 16 bit 才能完整保存。

乘积位数

n bit 与 n bit 相乘，结果不一定还能放进 n bit。若只保留低 n bit，高位会被截断。

## 有符号乘法

有符号整数使用Booth 算法直接处理补码乘法。

每轮 Booth 乘法的核心流程是：

查看 Y当前的最低位$Y_{0}$与其右边的 $Y_{-1}$(上一轮移出去的$Y_{0}$，初始值为0)。
1. 若为 01，则 P = P + X。
2. 若为 10，则 P = P - X。
3. 若为 00 或 11，则 P 不变。
将 P | Y | Y-1 整体算术右移一位。
重复 n 次后，P | Y 保存补码乘积。

引入$Y_{0}Y_{-1}$的思想是：把连续的一串 1 看成两个边界的差。

Example

01001B = +10000B - 1000B + 10B - 1B > 原本连续多个 `1` 需要多次加法；Booth 算法只在边界处做加减。`00` 和 `11` 都说明当前没有遇到边界，所以不操作。

Booth 算法为什么能处理有符号数

补码的符号位本来就有负权重。Booth 算法用“加一段的开始、减一段的结束”来重写乘数的权重展开，因此可以直接在补码位串上得到有符号乘积。

# 除法

进入除法过程前，必须先做入口判定：

只有这些情况都排除后，才需要进入逐位试减的除法过程。也就是恢复余数除法。

使用寄存器说明如下。

恢复余数除法的核心流程是：

将 R | Q 整体左移一位。
试做 R = R - Y。
1. 若 R 非负，说明够减，当前商位记 1。
2. 若 R 为负，说明不够减，恢复原来的 R，当前商位记 0。
重复 n 次后，Q 中保存商，R 中保存余数。

试减需要判断正负

恢复余数除法中，R - Y 的结果可能为负。为了判断是否够减常把 R 看成带符号或带扩展位的部分余数寄存器。

商溢出

商溢出发生在商形成或结果写回阶段。若最终得到的商无法放入目标商寄存器，就不能按正常结果写回，应触发商溢出异常。

以上是无符号数的除法的过程。
有符号除法一般先对绝对值做无符号除法，再根据操作数的符号恢复商和余数的符号，结果按补码保存。若结果超出补码可表示范围，也会发生商溢出；典型情况是 n bit 补码的最小负数除以 -1。