除法器

复习

1. 第十三章：掌握了补码
2. 第十四章：设计完成了减法器，本质是加上一个负数（补码）
3. 第十五章：设计完成了乘法器，本质是多次加法

TL;DR

• 除法就是不断地减，看能减几次
• 二进制除法更简单：商非 0 即 1，每次只需判断“够不够减“
• 除法器主要由减法器、移位器和控制电路组成

正文

二进制除法

　　二进制的除法大体上与十进制除法相同，但比十进制简单。因为每一位商只能是 1 或 0，不用想“能减几次“，每次只需判断“够不够减“：

• 够减，商记 1，减掉
• 不够减，商记 0，不动

　　就像笔算除法需要纸和笔，除法器也需要几样工具：

1. 减法器：判断“能不能减“
2. 移位器：对被除数（余数）和商进行移位，和乘法器类似，但方向不同
3. 控制电路：控制整个除法过程、判断何时结束、处理除数为 0 等特殊情况

具体步骤

　　我们用 15 ÷ 3 = 5 来看除法器的工作过程。被除数 1111（15），除数 0011（3）。

　　思路是“从高位到低位，一位一位地试“：

1. 先看被除数最高位 1。1 < 3，不够减，商记 0，余数仍是 1
2. 再拉下一位，余数变成 11（3）。3 >= 3，够减，商记 1，余数变为 11 - 11 = 0
3. 再拉下一位 1。1 < 3，不够减，商记 0，余数仍是 1
4. 再拉下最后一位，余数变成 11（3）。够减，商记 1，余数变为 0

　　把每一步的商按顺序拼起来：

       0101
     ______
0011 ) 1111
       0000      第 1 位：不够减，商 0
       ————
        111
        011      第 2 位：够减，商 1
        ————
          01
          00     第 3 位：不够减，商 0
          ————
           11
           11    第 4 位：够减，商 1
           ————
            0

　　最终商是 0101（5），余数是 0。和十进制笔算一模一样，只是借位、试商都变成了 0 和 1 的游戏。

除法器的工作原理

　　把上面这套流程“固化“成电路：

1. 初始化：被除数放进寄存器，商清零，设一个计数器记录还要试几位
2. 重复以下步骤（每一位一次）：
   • 把被除数（余数）左移一位，拉下被除数的下一位
   • 判断当前值是否 >= 除数：够减就减去除数、商末位置 1；不够减就保持原值、商末位置 0
   • 计数器减一
3. 计数器归零时结束。重复次数等于被除数的位数

特殊情况

　　除法比乘法多了几个要小心的地方：

1. 除数为 0：数学上没有意义，硬件上必须在开始前检测，触发异常或中断
2. 溢出：商的位数装不下时会发生（比如 8 位除法里，255 ÷ 1 的商是 255，还算装得下；但某些组合会超出），需要检测
3. 符号处理：带符号数除法，先确定结果符号（同号为正、异号为负），再取绝对值相除，最后转回补码

　　这里“每次试商都要真减一次、不够减还要恢复“的做法，虽然能跑，但有点慢。怎么优化，留到《乘除法的优化》一章。

思考题

　　用上面“一位一位试“的思路，算一算 13 ÷ 4（二进制 1101 ÷ 0100），商和余数各是多少？

小结

知识点

• 除法就是不断地减
• 二进制除法只需判断“够不够减“
• 除法器的组成：减法器、移位器、控制电路
• 除数为 0、溢出、符号处理等特殊情况

参考资料

1. 计算机是如何做除法的
2. Wikipedia(zh)：除法：除法的基本概念
3. Wikipedia(zh)：长除法：详细的除法算法介绍

思考题答案（仅供参考）

　　1101 ÷ 0100，除数 0100（4）：

• 先拉最高位 1：1 < 4，商 0，余 1
• 拉下一位：11（3）< 4，商 0，余 11
• 拉下一位：110（6）>= 4，商 1，余 110 - 100 = 010
• 拉下最后一位：101（5）>= 4，商 1，余 101 - 100 = 001

　　所以商是 0011（3），余数是 001（1）。验证：13 = 4 × 3 + 1。

协议

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

封面图

设计师 | 南国微雪