除法器
复习
- 累加器：把寄存器输出接回运算器，构成能连续累加的累加器
- 状态机：时序逻辑用状态和输入决定下一步动作
- 乘法器：乘法拆成移位和多次加法，并用状态机推动
TL;DR
- 除法可以拆成移位、比较与多次减法
- 每一轮只回答“这一次够不够减”
- 商记录每轮的答案，最后没有分完的部分就是余数
正文
乘法是在问“要加几份”，除法则是在问“最多能拿走几份”。
比如 13 ÷ 3。在十进制里，我们知道能拿走 4 份，还剩 1。可电路不会凭感觉就猜出 4——它不会感觉，但它会减法，也会判断一个数够不够减。只要把这两个本事用对，除法就能一步步试出来。
一位一位试
把 13 写成二进制 1101，3 写成 0011。我们从高位开始，把被除数逐位“带下来”，就像做十进制长除法：
- 当前只有
1，比 3 小，商这一位写 0 - 再带下一位，得到
11，刚好够减 3，商写 1，余数变 0 - 带下
0，仍然不够减，商写 0 - 带下最后的
1，仍然不够减，商写 0，余数留下 1
得到的商是 0100，也就是 4；余数是 1。验证一下：3 × 4 + 1 = 13。
竖式里的每一步，电路都可以用同一个问题概括：
当前部分够不够减去除数？
够，就减并在商里写 1；不够，就保留原数并写 0。然后移一位，继续问下一轮。
除法器需要什么
于是，一个最简单的除法器只要会做这些事：
- 用减法器试减
- 根据结果决定保留原数还是减后的数
- 把商左移并补进新的 0 或 1
- 重复固定次数
你可能已经发现：乘法器和除法器长得非常像。它们都没有发明新的基本运算，只是让加减法器配合移位，一轮一轮地工作。机器做复杂运算的秘诀，多半是把一个难题拆成一串它已经会做的小动作。
一个不能算的数
除数如果是 0，“够不够减”就永远没有意义。因为任何有限的商乘 0 都得不到原来的被除数，试下去也永远不会有结果。所以控制电路必须在运算开始前检测并报告除零，而不是让状态机无休止地试下去。
这其实是除法比乘法更麻烦的地方：它多了一种“合法输入却无法计算”的情况。处理它的方式，是提前检查、提前报错——这个思路以后还会反复出现。
乘法器和除法器已经证明，ALU、寄存器、时钟与状态机可以合作完成多步任务。下一章，我们把少量寄存器扩展成能按地址保存许多数据的存储器。
思考题 1
计算
1110 ÷ 0011。商和余数分别是多少？如何用“除数 × 商 + 余数”检查答案？
思考题 2
为什么除法器必须在开始前检查除数是不是 0，而乘法器却不需要类似的操作？
小结
知识点
- 二进制长除法
- 移位减法除法器
- 商与余数的来源
- 除零必须单独处理
参考资料
- Wikipedia(zh)：除法器：数字除法器的实现方式
- Wikipedia(zh)：带余除法：商与余数的关系
思考题答案（仅供参考）
思考题 1
1110₂ 是 14，0011₂ 是 3，所以商为 0100（4），余数为 0010（2）。检查：3 × 4 + 2 = 14。
思考题 2
因为乘法对任何除数都不会出现“无法计算”的情况，任意两个数相乘都有有限的结果；而除法的除数为 0 时，根本不存在满足条件的商。所以乘法器不必做额外检查，除法器则必须提前拦截这种输入。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪