乘法器

复习

• 寄存器：多个触发器并排，形成能保存多位数据的寄存器
• 累加器：把寄存器输出接回运算器，构成能连续累加的累加器
• 状态机：时序逻辑用状态和输入决定下一步动作

TL;DR

• 二进制乘法就是“检查乘数的每一位，再决定是否累加”
• 左移一位相当于乘 2
• 一个加法器配合移位与重复控制，就能完成乘法

正文

　　要算 3 × 5，最笨的办法是把 3 连着加五次。这个办法确实能算，但 5 如果换成五百万，我们大概会先失去耐心。

　　乘法的本质是“重复加法”，可重复太多次就不划算了。二进制给了我们一条近路。

把乘法拆成加法

　　先把两个数写成二进制：

3 = 0011
5 = 0101

　　0101 的意思是 1 + 4，所以 3 × 5 可以改写成：

3 × (1 + 4) = 3 + (3 × 4)

　　现在只需要算两块：一份 3，和一份 3 × 4。而在二进制里，乘 2 只需左移一位，乘 4 就左移两位，乘 2ⁿ 就左移 n 位。移位不花什么力气，这比加五百万次便宜多了。

0000 0011        3
0000 1100       12
---------
0000 1111       15

　　这和十进制竖式乘法其实是一回事，只是二进制的每一位只有 0 和 1：遇到 0 就什么也不加，遇到 1 才把当前的被乘数加进结果。乘数的每一位，就是在问我们：“这一份要不要？”

让加法器反复工作

　　顺着这个思路，准备三个位置：

• 被乘数：开始放 3，每轮左移一位
• 乘数：开始放 5，每轮右移一位
• 结果：开始为 0，用来保存已经累加的部分

　　每一轮只做三件事：

1. 看乘数最右边是不是 1
2. 如果是 1，就把当前的被乘数加进结果
3. 被乘数左移、乘数右移，进入下一轮

　　对 3 × 5 来说：

　　三轮以后，结果就是 15。整个过程只用到了加法、移位和“看一眼最低位”——全都是我们已经会做的动作。

为什么结果要更宽

　　两个 4 位无符号数最大都是 15，而 15 × 15 = 225，需要 8 位才能装下。所以 n 位乘 n 位，通常要为完整乘积准备 2n 位。这也提醒我们：位宽是电路设计里一条一直要盯着的红线。

　　现在回看，“三个位置”可以各由寄存器承担，ALU 负责加法，简单的移位线路负责移动各位，状态机则依次发出“检查、累加、移位、继续”的控制信号。时钟每走一拍，乘法器就前进一步，直到所有乘数位都检查完毕。

　　这一次，我们不是先描述算法、以后再补零件，而是已经握着组成它的全部部件了。下一章，用同样的寄存器、ALU 和状态机，来完成它的逆运算——除法。

思考题 1

　　用“检查最低位、按需累加、左右移位”的方法，计算 0010 × 0110。哪些轮次真的发生了加法？

思考题 2

　　这个方法里，乘数右移、被乘数左移，其实是在让两者“错位对齐”。如果改成乘数和被乘数都不动，而是每次把结果左移，能得到同样的乘积吗？

小结

知识点

• 二进制竖式乘法
• 左移一位相当于乘 2
• 移位加法乘法器
• n 位乘法的完整结果最多需要 2n 位

参考资料

1. Wikipedia(zh)：乘法器：数字乘法器的实现方式
2. Wikipedia(zh)：移位运算：左移与右移的含义

思考题答案（仅供参考）

思考题 1

　　0110 从右向左的各位分别是 0、1、1、0，所以只有第 2、3 轮发生加法：0100 + 1000 = 1100，也就是 12。

思考题 2

　　可以。每次把结果左移一位，再按乘数当前位决定加不加被乘数，最终乘积相同。这本质上还是“每一位对应一个移位后的被乘数”的思路，只是把移位放在了结果上。两种写法等价，选哪种取决于电路实现起来哪种更方便。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪