乘法器

复习

1. 第十一章：设计完成了全加器，可以串联构成多位加法器
2. 第十三章：掌握了补码，理解了它可以统一加减法
3. 第十四章：设计完成了减法器，本质是加上一个负数（补码）

TL;DR

• 乘法本质是多次加法
• 二进制乘法更简单：只需要“逐位相乘 + 移位 + 相加“
• 乘法器由与门阵列、移位器和加法器组成

正文

本质

　　加减法有了，乘除法呢？有了乘法，而除法是乘法的逆运算，问题应该也不大。

　　回忆小学怎样算乘法。列竖式，相加：

  23
×  5
----
 115

　　而乘法本质是反复加法，所以这实际上是：

  23 × 5 = 23 + 23 + 23 + 23 + 23

　　十进制可以这样算，二进制呢？

逐位相乘

　　不妨来试试： 3 × 5 = 15。简单起见，使用无符号数，没有符号位。

    0011   （3 的无符号二进制）
×   0101   （5 的无符号二进制）
--------    <-- # 表示占位符，没有意义
    0011    (被乘数 × 1)
   0000#    (被乘数 × 0，左移一位)
+ 0011##    (被乘数 × 1，左移两位)
 0000###    (被乘数 × 0，左移三位)
--------
    1111   （15 的无符号二进制）

　　竖式也能得出正确结果：0011 × 0101 = 1111_{2 进制无符号}，也即 15₁₀。

　　那就好办了：让一个二进制数，与另一个二进制数的 每一位 相乘，然后做竖式一样的 移位，最后加在一起。

　　上面的竖式默认两个数都是无符号数。有符号数（尤其是负数）的乘法要复杂一些，不能直接把补码按上面的方法乘。不过别担心，先把无符号乘法学明白，减法器和补码我们已经有了，符号问题总有办法处理。

　　相乘这一步，仔细观察可以用 and（与门）解决，那—— 移位 呢？

移位

　　上面逐位相乘的移位，最简单的方式就是在末位后面补零、同时丢掉最高位：0011 不补零，0000 补一个，0011 补两个。

　　而对有符号数进行移位时，特别是右移，最高位需要补上符号位，不然负数就变成正数了。也就是说：对 1010 进行右移，结果应该为 1101。

思考题 1

　　我们现在只有加法器，应该怎样移位和补位？以及， 设计一个最简单的乘法器，真的需要移位吗？

乘法器的构成

　　根据上面的分析，乘法器需要以下部件：

1. 与门阵列：
   • 判断乘数的每一位是否为 1
   • 为 1 就输出被乘数，为 0 就输出全 0
2. 移位器：对每一步的结果左移，移几位取决于当前处理的是乘数的第几位
3. 加法器：累加每一步的结果，可以复用之前设计的加法器

具体实现

　　以 3(0011) × 5(0101) 为例：

1. 乘数最低位为 1：0011 × 1 = 0011，不移位
2. 乘数次低位为 0：0011 × 0 << 1 = 0000
3. 乘数第三位为 1：0011 × 1 << 2 = 1100
4. 乘数最高位为 0：0011 × 0 << 3 = 0000

　　最后全部相加：

   0011
+ 0000
+ 1100
+ 0000
-------
   1111 (15)

　　一个能用的乘法器就出来了。

　　不过，这种“老老实实逐位加“的办法在乘数有很多连续 1 的时候会非常慢（比如 64 位全 1，就要加 64 次）。针对它的优化（Booth 算法、华莱士树）属于进阶内容，我们放到《乘除法的优化》一章。

思考题 2

　　如果要计算带符号数的乘法，需要注意什么？

小结

知识点

• 乘法的本质是多次加法
• 二进制乘法的基本步骤：逐位相乘、移位、相加
• 乘法器的基本构成：与门阵列、移位器、加法器

参考资料

1. Wikipedia(zh)：乘法器：乘法器的工作原理
2. Wikipedia(zh)：位操作#移位：二进制移位
3. BiliBili：计算机怎样计算乘法

推荐

• Bilibili：计算机如何计算乘法

思考题答案（仅供参考）

思考题 1

1. 移位可以使用 or 和 xor 门，最简化的做法是把输入直接与输出错位相连。错位直接相连比用逻辑门效率更高、速度更快。

2. 其实最简单的乘法器不需要移位，只需要错位相加，把低位直接输出即可。

思考题 2

　　带符号数乘法需要注意：

1. 结果的符号由两个操作数的符号决定
2. 可以先把操作数转换为绝对值做乘法
3. 再根据“同号得正、异号得负“确定符号
4. 若结果为负，转回补码表示

协议

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

封面图

设计师 | 南国微雪