Fast Modulus Operation and Using Unsigned Ints as an Optimization

This is another pretty well-known trick; but there is often a few misconceptions with it.

If you are using the modulus operator '%' with a power of 2 value '2^n', then you can do the same operation with a bitwise AND with 2^n-1.

// Normal Mod Operation
void mod(unsigned int& x) {
  x = x % 4;
}

// Optimized Mod Operation
void mod(unsigned int& x) {
  x = x & 3;
}

It is very important to note that this only works with positive/unsigned values.
If x was '-6' for example, the correct value returned should be '-2', but with the optimized mod it would return '2'.

The optimized mod trick however is very useful as perhaps one of the most common uses of Mod is to check if a number is odd or even:

// Normal isEven Operation
bool isEven(int x) {
  return !(x % 2);
}

// Optimized isEven Operation
void isEven(int x) {
  return !(x & 1);
}

This works regardless if the input is positive/unsigned, and is much faster than using the modulus operator.

The way the Modulus operator works in x86-32 is it has to do a Div operation, and get the remainder; Div is almost always a slow operation on any architecture.


I also wanted to point out something else.
The misconception some people have is that the compiler already will optimize something like "x = x % 2" into "x = x & 1", well the real answer is not-always.

As I already said, the optimization only works for positive/unsigned values, so if you declare x as a normal signed-int, then the compiler can't safely optimize the operation into an AND.
This is why I wanted to point out that using "Unsigned Int" can be an optimization because the compiler will be able to change such mod operations into bitwise ANDs.

If you leave the values as signed, the compiler either does one of 2 things:
1) Will just compile it using a div and get the remainder.
2) Will compile code that checks the sign bit of value, does the optimized AND, and negates the value if the original value was negative.

That is, the compiler will do something like this:

// What the compiler might generate for
// "x = x % 2;" with signed values
if (x < 0) {
    x =  x & 1;
    x = -x;
}
else x = x & 1;

Many times I have seen code where performance has increased dramatically from removing modulus operations in favor of bitwise ANDs or other logic.

For example, if you were to have a loop like this:

for(int i = 0; i < 100000; i++) {
    someVar++;
    someVar%=7;
    // ... Do more stuff
}

You can make it much faster by doing this:

for(int i = 0; i < 100000; i++) {
    someVar++;
    if (someVar >= 7) someVar = 0;
    // ... Do more stuff
}