0

I've seen that gcc does a great job in optimizing integer divisions with a constant divisor.

E.g.

uint64_t f(uint64_t x)
{
    return x / 1000;
}

uint64_t f2(uint64_t x)
{
    return x / 10000;
}

becomes:

f:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        shr     rax, 3
        movabs  rdx, 2361183241434822607
        mul     rdx
        mov     rax, rdx
        shr     rax, 4
        pop     rbp
        ret
f2:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-8], rdi
        mov     rax, QWORD PTR [rbp-8]
        movabs  rdx, 3777893186295716171
        mul     rdx
        mov     rax, rdx
        shr     rax, 11
        pop     rbp
        ret

It seems all divisions can be reduced to a shift + multiplication + shift (not always are all of those operations included).

How is this obtained and how can I get manually the required numbers for those three operations? I specifically need to know this for uint64_t,

Thanks a lot

Kevin Meier
  • 2,339
  • 3
  • 25
  • 52
  • 1
    Observe that 2^(64+3+4)=2361183241434822606848≈2361183241434822607*1000 and 2^(64+11)=37778931862957161709568≈3777893186295716171*10000. – n. m. could be an AI Jul 18 '23 at 21:11
  • 1
    Does this answer your question? [Why does GCC use multiplication by a strange number in implementing integer division?](https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi) – Nate Eldredge Jul 20 '23 at 05:44
  • @NateEldredge This answer indeed covers most of what I need to know (e.g. libdivide is quite helpful) – Kevin Meier Jul 20 '23 at 07:14

0 Answers0