How to avoid Modulo Operators

Mostly programmers are aware of modulo (%) and integer div (/) operators regardless of language they used. They are least used arithmetic operator in most programming languages. Modern off-the-shelf processors have built in instructions to perform such operations.

What is Modulo Operator:

In computing, the modulo operation finds the remainder after division of one number (dividend) by another (divisor) -- Wikipedia

One common use case for this operator is to check if a number is even or odd. If remainder of a number is Zero when 2 divide it then it is an Even number else it is Odd.

0 % 2 = 0
1 % 2 = 1
2 % 2 = 0
3 % 2 = 1
4 % 2 = 0
5 % 2 = 1

The result of modulo operator can never be greater than divisor, it will always be one lesser then second number. The reason this happens is because division is all about fair sharing.

How to avoid Modulo operator:

I modern architecture, Division operator may take several clock cycles to perform its operation. Modulo operators can be easily translated into Bitwise operators. If a divisor is power of 2 then it can be replaced by bitwise AND operator. It will take only one CPU cycle. for example:

int remainder = value % 1024;

it can be translated into:

int remainder = value & 0x3FF;
int remainder = value & (1024-1);

in general, If divisor n is power of 2, the modulo operators can be translated into bitwise AND with divisor - 1.

What is the real impact of modulo operator:

Marco Ziccardi wrote a program to answer this question:

int main(int argc, char** argv) { 
    int remainder;
    int value = 1301081;
    int divisor = 1024;
    int i = 0;
    while (i < 10000000) {
        remainder = value % divisor;
        i++;
    }
}

And compared its execution times with the same program implemented using binary AND (&) operator. Results are shown below (1000 runs of the program for both % and & versions):

As you can see, in the average case the program with the modulo operation is 62% slower than the one using & operator.

Conclusion:

It is not always possible to avoid modulo operator in the favor of bitwise.

Written on April 15th, 2018 by Abdul Basit