measures the runtime of different variants of the integer division

divisions.cpp

#include <stdio.h>
#include <stdint.h>
#include <time.h>

template<typename Fn>
void measure(Fn fn) {
    clock_t c1 = clock();
    fn();
    clock_t c2 = clock();
    printf("time: %7.3lf\n", (c2 - c1) / (double)CLOCKS_PER_SEC);
}

#define MAKE_CALC(fname, fdiv) \
__attribute__((noinline)) \
uint64_t fname() { \
    uint64_t r = 0; \
    for (volatile uint32_t x = 1; x < 0x7fffffff; ++x) { \
        r += fdiv(0x7fffffff - (x >> 16), x); \
    } \
    return r; \
}

uint32_t divByDiv(uint32_t x, uint32_t y) {
    return x / y;
}

MAKE_CALC(calcByDiv, divByDiv)

uint32_t divByDouble(uint32_t x, uint32_t y) {
    return (uint32_t)((double)x / y);
}

MAKE_CALC(calcByDouble, divByDouble)

uint32_t divByDoubleHack(uint32_t x, uint32_t y) {
    union {
        double dd;
        uint64_t du;
    } xd, yd;
    xd.du = 0x4330000000000000 | x;
    yd.du = 0x4330000000000000 | y;
    return (uint32_t)((xd.dd - 0x1p52) / (yd.dd - 0x1p52));
}

MAKE_CALC(calcByDoubleHack, divByDoubleHack)

uint32_t divByLoopIf(uint32_t x, uint32_t y) {
    uint32_t xh = 0;
    uint32_t r = 0;
    xh = (xh << 1) + (x >> 31);
    x <<= 1;
    for (int n = 0; n < 31; ++n) {
        if (xh >= y) {
            r += 1;
            xh -= y;
        }
        xh = (xh << 1) + (x >> 31);
        x <<= 1;
        r <<= 1;
    }
    r += xh >= y;
    return r;
}

MAKE_CALC(calcByLoopIf, divByLoopIf)

uint32_t divByLoopBit(uint32_t x, uint32_t y) {
    uint32_t xh = 0;
    uint32_t r = 0;
    xh = (xh << 1) + (x >> 31);
    x <<= 1;
    for (int n = 0; n < 31; ++n) {
        uint32_t k = xh >= y;
        r += k;
        xh -= y & (-k);
        xh = (xh << 1) + (x >> 31);
        x <<= 1;
        r <<= 1;
    }
    uint32_t k = xh >= y;
    r += k;
    return r;
}

MAKE_CALC(calcByLoopBit, divByLoopBit)

uint32_t divByLoopIfLong(uint32_t x, uint32_t y) {
    uint64_t r = x;
    uint64_t d = (uint64_t)y << 32;
    uint32_t q = 0;
    for (int n = 0; n < 32; ++n) {
        r <<= 1;
        q <<= 1;
        if (r >= d) {
            q += 1;
            r -= d;
        }
    }
    return q;
}

MAKE_CALC(calcByLoopIfLong, divByLoopIfLong)

int main() {
    measure(
        []() {
            printf("divByDoubleHack %lu\n", calcByDoubleHack());
        });
    measure(
        []() {
            printf("divByDouble     %lu\n", calcByDouble());
        });
    measure(
        []() {
            printf("divByDiv        %lu\n", calcByDiv());
        });
    measure(
        []() {
            printf("divByLoopIf     %lu\n", calcByLoopIf());
        });
    measure(
        []() {
            printf("divByLoopIfLong %lu\n", calcByLoopIfLong());
        });
    measure(
        []() {
            printf("divByLoopBit    %lu\n", calcByLoopBit());
        });
    return 0;
}

/*
// AMD Ryzen 7 5800H
// g++ div.cpp -O3 -o div
divByDoubleHack 46475774434
time:   2.243
divByDouble     46475774434
time:   2.356
divByDiv        46475774434
time:   2.936
divByLoopIf     46475774434
time:  32.655
divByLoopIfLong 46475774434
time:  33.075
divByLoopBit    46475774434
time:  72.523
*/