algorithm - 这是执行整数除法函数的聪明方法还是愚蠢方法？

Question

我是一名计算机科学专业的学生，​​对汇编语言如何处理整数除法函数很感兴趣。似乎简单地把分子加起来，同时给出除法和模数，太不切实际了，所以我想出了另一种除法方法，使用位移、减法和 2 个查找表。

基本上，该函数采用分母，并根据 2 的最高次方生成“ block ”。因此除以 15 生成二进制 block 4，除以 5 生成二进制 block 3，等等。然后生成第一个 2 ^分母的 block 大小倍数。对于每个倍数，将第一个 block 之后的值写入查找表，以第一个 block 的值作为键。

示例:二进制 5 的倍数 - block 大小 3(八进制)

000 000 **101** - 5 maps to 0    
000 001 **010** - 2 maps to 1  
000 001 **111** - 7 maps to 1  
000 010 **100** - 4 maps to 2  
000 011 **001** - 1 maps to 3  
000 011 **110** - 6 maps to 3  
000 100 **011** - 3 maps to 4  
000 101 **000** - 0 maps to 5

所以实际的过程包括获取第一个 block ，在第一个 block 上进行左移，然后减去 block 映射到的值。如果结果数为 0，则它可以完全整除，如果该值变为负数，则不能整除。

如果您添加另一个枚举查找表，在其中将值映射到计数器，您可以计算除法的结果!

示例:5 的倍数

5 maps to 1  
2 maps to 2  
7 maps to 3  
4 maps to 4  
1 maps to 5  
6 maps to 6  
3 maps to 7  
0 maps to 8  

然后剩下的就是将每个 block 映射到计数器表，你就有了答案。
这种方法有一些问题。

1. 如果答案不能完全整除，则函数返回垃圾。
2. 对于高整数值，这将不起作用，因为 5 block 大小将在 32 位或 64 位整数的末尾被截断。
3. 它比 C 中的标准除法慢大约 100 倍。
4. 如果分母是除数的因数，那么您的 block 必须映射到多个值，您甚至需要更多 表。这可以通过素数分解来解决，但是我读过的所有关于简单/快速素数分解的方法都涉及除法，这违背了这样做的目的。

所以我有两个问题:首先，是否已经有类似的算法？我环顾四周，似乎找不到任何类似的东西。第二，实际的汇编语言如何处理整数除法？

抱歉，如果有任何格式错误，这是我第一次在 stack overflow 上发帖。

Answer 1

抱歉这么晚才回答。好的，首先关于您的问题的评论者:他们认为您正在尝试通过在汇编 中使用不同的指令来执行汇编内存 DIV 或 IDIV 所达到的目的。在我看来，您想知道 DIV 和 IDIV 选择的操作码如何在硬件中实现除法。据我所知，英特尔使用 SRT 算法(使用查找表)，而 AMD 使用 Goldschmidt 算法。我认为你所做的与 SRT 类似。您可以在这里查看它们:

http://en.wikipedia.org/wiki/Division_%28digital%29