这是执行整数除法函数的聪明还是愚蠢的方法？
我是计算机科学专业的学生，对汇编语言如何处理整数除法函数感兴趣。看起来简单地加分子，同时给出除法和模，太不切实际了，所以我想出了另一种使用位移位、减法和两个查找表来除法的方法。
基本上，该函数采用分母，并根据 2 的最高幂生成“块”。因此，除以 15 生成 4 的二进制块，除以 5 生成 3 的二进制块，依此类推。然后生成第一个 2^block-分母的大小倍数。对于每个倍数，将第一个块之后的值写入查找表中，并以第一个块的值作为关键字。
示例：二进制中 5 的倍数 - 块大小 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
因此，实际过程包括获取第一个块、对第一个块进行左移位，然后减去块映射到的值。如果结果为 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
那么剩下的就是将每个块映射到计数器表，然后您就得到了答案。
这种方法存在一些问题。
- 如果答案不能完全整除，则该函数返回垃圾。
- 对于高整数值，这不起作用，因为 5 块大小将在 32 位或 64 位整数末尾被截断。
- 它比 C 中的标准除法慢大约 100 倍。
- 如果分母是除数的因数，那么您的块必须映射到多个值，甚至需要更多表。这可以通过素因数分解来解决，但是我读过的所有关于简单/快速素因数分解的方法都涉及除法，这违背了它的目的。
所以我有两个问题：首先，是否已经有类似的算法？我环顾四周，似乎找不到类似的东西。其次，实际的汇编语言如何处理整数除法？
抱歉，如果有任何格式错误，这是我第一次在 Stack Overflow 上发帖。
I'm a Computer Science major, interested in how assembly languages handle a integer divide function. It seems that simply adding up to the numerator, while giving both the division and the mod, is way too impractical, so I came up with another way to divide using bit shifting, subtracting, and 2 look up tables.
Basically, the function takes the denominator, and makes "blocks" based on the highest power of 2. So dividing by 15 makes binary blocks of 4, dividing by 5 makes binary blocks of 3, etc. Then generate the first 2^block-size multiple of the denominator. For each multiple, write the values AFTER the first block into the look up table, keyed by the value of the first block.
Example: Multiples of 5 in binary - block size 3 (octal)
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
So the actual procedure involves getting the first block, left bit-shifting over the first block, and subtracting the value that the blocks maps to. If the resulting number comes out to 0, then it's perfectly divisible, and if the value becomes negative, it's not.
If you add another enumeration look up table, where you map the values to a counter as they come in, you can calculate the result of the division!
Example: Multiples of 5 again
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
Then all that's left is mapping every block to the counter-table, and you have your answer.
There are a few problems with this method.
- If the answer isn't perfectly divisible, then the function returns back junk.
- For high Integer values, this won't work, because a 5 block size will get truncated at the end of a 32 bit or 64 bit integer.
- It's about 100 times slower than the standard division in C.
- If the denominator is a factor of the divisor, then your blocks must map to multiple values, and you need even more tables. This can be solved with prime factorization, but all the methods I've read about easy/quick prime factorization involve dividing, defeating the purpose of this.
So I have 2 questions: First, is there an algorithm similar to this out there already? I've looked around, and I can't seem to find any like it. Second, How do actual assembly languages handle Integer division?
Sorry if there are any formatting mistake, this is my first time posting to stack overflow.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
抱歉这么晚才回复。好的，首先关于您的问题的评论者：他们认为您正在尝试通过在汇编中使用不同的指令来实现汇编记忆 DIV 或 IDIV 所实现的功能。对我来说，您似乎想知道 DIV 和 IDIV 选择的操作码如何在硬件中实现除法。据我所知，Intel 使用 SRT 算法（使用查找表），AMD 使用 Goldschmidt 算法。我认为你所做的与SRT类似。您可以在这里查看它们：
Sorry i answer so late. Ok, first regarding the commenters of your question: they think you are trying to do what the assembly memonic DIV or IDIV achieves by using different instructions in assembly. To me it seems you want to know how the op-codes that are selected by DIV and IDIV achieve division in hardware. To my knowledge Intel uses the SRT algorithm (uses a lookup-table) and AMD uses the Goldschmidt algorithm. I think what you are doing is similar to SRT. You can take a look at both of them here: