二进制数的快速除法算法

Question

我目前正在使用Logisim(即仅逻辑门)构建一个16位ALU,并且我被困在一个除法过程中.我目前只使用简单的标准"除法算法循环"(如下所示):

1. 读取输入值;
2. 比较输入值.等到比较过程结束;
3. 如果A <B转到步骤10.如果A≥B,转到下一步;
4. 从A中减去B;
5. 等到减法过程结束;
6. 添加一个来计算;
7. 等到计数过程结束;
8. 从减法过程写入值到输入;
9. 转到第1步;
10. 答案是计数余数A.

然而,这对于具有大答案的过程需要很长时间(重复300次滴答循环65,000次并不好玩).我只是想知道是否有类似的算法可以使用逻辑门实现更快(专门使用加法和/或减法和/或乘法以及任何布尔逻辑).任何帮助或想法将不胜感激!弗雷泽

Answer 1

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

当然，这只是一个粗略的轮廓。