Integer division can be decomposed in a bitshift and a multiplication

fastDiv.cpp

/*
When I was looking at the disassembly of my compiler, I noticed that it decided to, instead of
dividing by 3, multiply by 2863311531.
At first I was puzzled by this, but it wasn't as complicated as I thought.
So it turns out that an integer division can be decomposed in two operatations:
1) A bit shift: that's just deviding by a power of 2
2) A multiplication that overflows
The compiler dicides to do this because division is an expensive operation for CPUs
So here I wrote some code that computes the right pair of values for the given divider
*/

#include <iostream>

using namespace std;

void calcFastDivOperands(uint64_t& shift, uint64_t& mul, uint64_t div)
{
    shift = 0;
    while((div & 1) == 0) {
        div >>= 1;
        shift++;
    }
    
    mul = 1;
    uint64_t p = div;
    for(int i=0; i<64; i++)
    {
        mul *= p;
        p *= p;
    }
}

uint64_t fastDiv(uint64_t a, uint64_t b)
{
    uint64_t shift, mul;
    calcFastDivOperands(shift, mul, b);
    a >>= shift;
    a *= mul;
    return a;
}

int main()
{
    uint64_t x = fastDiv(620, 10);
    cout << x << endl;
}