二进制数的快速除法算法

Question

我目前正在使用Logisim（即仅使用逻辑门）构建一个16位ALU，但卡在了除法过程上。我目前只是使用简单的标准“除法算法循环”（如下所示）：

1. 读取输入值;
2. 比较输入值。等待比较过程完成;
3. 如果A < B，请转到步骤10。如果A≥B，请继续下一步;
4. 从A中减去B;
5. 等待减法过程完成;
6. 将计数加1;
7. 等待计数过程完成;
8. 将减法过程中的值写入输入;
9. 回到步骤1;
10. 答案是商为count，余数为A

然而，这对于具有大答案的过程来说需要很长时间（重复一个300周期65,000次并不好玩）。我想知道是否有类似的算法更快（仅使用加法和/或减法和/或乘法和任何布尔逻辑），可以使用逻辑门实现。任何帮助或思路都将不胜感激！Fraser

- Fraser Price

---

肯定还有其他的除法算法。你看过哪些算法，为什么它们不适合你的工作？ - user395760

Answer 1

使用长除法。在二进制中，没有乘法，因为每个位位置的商只能是1或0。所以可以实现为条件减法（如果结果非负，则减去）和移位。

当然，这只是一个粗略的概述。

- rici

Answer 2

一个典型的32/16:16+16除法方法是将被除数存储在一对16位寄存器中（在操作过程中更新），而除数则单独存储在另一个寄存器中（不更新）。16次操作中，将被除数的上17位从除数中减去；如果借位，则舍弃结果并将除数左移一位，将0放入最低位。如果没有借位，则将结果存储到除数中，并将其左移，但将1放入最低位。经过16个这样的步骤，被除数寄存器的低16位将保存商，而高16位将保存余数。请注意，此操作仅适用于商可以用16位表示的情况。请注意，在实现32/16:16+16除法的处理器上，可以方便地通过16位量将任意大的数字进行除法运算，因为每个步骤的被除数的上16位应该是前一步骤的余数。

- supercat