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

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

我一直在读到divmul程序集操作,我决定通过用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?它是如何产生这个神奇的数字的,为什么所有的东西都能工作呢?


绝地无双
浏览 678回答 3
3回答

catspeake

除以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,&nbsp;x=4/5..然后将其表示为CCCCCCCCCCCCD以十六进制表示四舍五入(上一位后面的二进制数字将是1).
打开App,查看更多内容
随时随地看视频慕课网APP