除法器
复习
- 乘法可以拆成移位和多次加法
- 乘数的每一位决定“这一轮要不要加”
- 寄存器保存中间结果，状态机推动每一轮前进
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。
竖式里的每一步，电路都可以用同一个问题概括：
当前部分够不够减去除数？
够，就减并在商里写 1；不够，就保留原数并写 0。然后移一位，继续。
除法器需要什么
于是，一个最简单的除法器只要会做这些事：
- 用减法器试减
- 根据结果决定保留原数还是减后的数
- 把商左移并补进新的 0 或 1
- 重复固定次数
你可能发现了：乘法器和除法器长得很像。它们都没有发明新的基本运算，只是让加减法器配合移位，一轮一轮地工作。
一个不能算的数
除数如果是 0，“够不够减”永远没有意义。任何有限的商乘 0 都得不到原来的被除数，所以控制电路必须在运算开始前检测并报告除零，不能让状态机无休止地试下去。
补充：更快的除法器
按位试减的除法器很省电路，却要花许多个时钟周期。更复杂的除法器可以一次估计多位商，或者铺开更多减法与选择电路，让若干步骤同时推进。和乘法器一样，速度的代价通常是更大的面积与功耗。
我们的机器不需要收下所有优化。乘法器和除法器已经证明，ALU、寄存器、时钟与状态机可以合作完成多步任务。下一章，我们把少量寄存器扩展成能按地址保存许多数据的存储器。
思考题
计算
1110 ÷ 0011。商和余数分别是多少？如何用“除数 × 商 + 余数”检查答案？
小结
知识点
- 二进制长除法
- 移位减法除法器
- 商与余数的来源
- 除零必须单独处理
思考题答案（仅供参考）
1110₂ 是 14，0011₂ 是 3，所以商为 0100（4），余数为 0010（2）。检查：3 × 4 + 2 = 14。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪