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).