乘法器

复习

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

　　二进制给了我们一条近路。先把两个数写出来：

3 = 0011
5 = 0101

　　0101 表示 1 + 4，所以 3 × 5 也可以写成：

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

　　在二进制里，乘 2 只需左移一位，乘 4 就左移两位：

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

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

　　我们可以准备三个位置：

　　每一轮只做三件事：

　　对 3 × 5 来说：

轮次	乘数最低位	要不要加	结果
开始	-	-	`0000`
1	1	加 `0011`	`0011`
2	0	不加	`0011`
3	1	加 `1100`	`1111`

　　三轮以后，结果就是 15。

　　两个 4 位无符号数最大都是 15，而 15 × 15 = 225，需要 8 位才能装下。所以 n 位乘 n 位，通常要为完整乘积准备 2n 位。

　　上面的做法复用一个加法器，电路省，却要逐位检查乘数。追求速度的乘法器会让多个部分积同时相加，或者用 Booth 编码减少连续多个 1 带来的重复累加。它们没有改变乘法的结果，只是在用更多电路换更少时间。

　　极简机器保留最朴素的移位加法已经够用。以后再遇到硬件优化，也可以先问一句：它是在减少步骤，还是让更多步骤同时进行？

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

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

思考题

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

设计师 | 南国微雪