GCC为什么用奇数乘法来实现整数除法？

Question

GCC为什么用奇数乘法来实现整数除法？我一直在读到div和mul程序集操作，我决定通过用C编写一个简单的程序来查看它们的运行情况：文件分割.c#include <stdlib.h>#include <stdio.h>int main(){     size_t i = 9;     size_t j = i / 5;     printf("%zu\n",j);     return 0;}然后用以下方法生成汇编语言代码：gcc -S division.c -O0 -masm=intel但是看看生成的division.s文件，它不包含任何div操作！相反，它做了某种黑色魔术与比特移动和魔术数字。下面是计算i/5:mov     rax, QWORD PTR [rbp-16]   ; Move i (=9) to RAX movabs  rdx, -3689348814741910323 ; Move some magic number to RDX (?)mul     rdx                        ; Multiply 9 by magic number mov     rax, rdx                  ; Take only the upper 64 bits of the result shr     rax, 2                    ; Shift these bits 2 places to the right (?)mov     QWORD PTR [rbp-8], rax     ; Magically, RAX contains 9/5=1 now,                                    ; so we can assign it to j这里发生了什么事？GCC为什么根本不使用div？它是如何产生这个神奇的数字的，为什么所有的东西都能工作呢？

Answer 1

除以5等于乘1/5，这又与乘4/5和右移2位相同。有关的价值是CCCCCCCCCCCCD在十六进制中，它是4/5的二进制表示，如果放在十六进制点之后(即五分之四的二进制是0.110011001100反复出现-请参见下面的原因)。我想你可以从这里拿走它！你可能想去看看不动点算法(注意，它在结尾处被舍入为整数。

为什么乘法比除法快，除数固定时，这是一条更快的路。

看见倒数乘法，教程关于它是如何工作的详细的文章，用定点来解释。说明了该算法的工作原理，以及如何处理符号除法和模运算。

让我们考虑一下为什么0.CCCCCCCC...(六角)或0.110011001100...二进制是4/5。除以4(右移2位)，我们将得到0.001100110011...通过简单的检查，可以添加原始的0.111111111111...，显然等于1，同样的方式。0.9999999...小数等于1。因此，我们知道x + x/4 = 1，所以5x/4 = 1, x=4/5..然后将其表示为CCCCCCCCCCCCD以十六进制表示四舍五入(上一位后面的二进制数字将是1).