Calculate Module of negative values FASTER.

#cpp #algorithms #math

Many of us have attempted to calculate the absolute value of negative numbers at some point then went to Stackoverflow and tried to find an answer and probably found this code:

// C/C++
int module(int a, int b) {
    return ((a % b) + b) % b;
}

HOWEVER it is doing two divisions (module same thing for x86-cpus)
You probably know divisions is a terribly slow operation
Exactly 7-15 times slower than addition operation in modern cpus

BUT you can lower this division usage in your module calculation this way:

int module(int a, int b) {
    return (a % b) + (((a ^ b) >> 31) & a);
}

This way uses trick checks if a * b is negative but you won't gonna see any multiplication or '<' symbol:
((a ^ b) >> 31) this part does the job (a ^ b) is calculating a * b s symbol and '>> 31' this making sign bit to copy 31 times into all bits.