Trash Can of Code: Fast Modulus Operation and Using Unsigned Ints as an Optimization

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.

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'.

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.

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:

if (x < 0) {

    x =  x & 1;

    x = -x;

}

else x = x & 1;

Read full article from Trash Can of Code: Fast Modulus Operation and Using Unsigned Ints as an Optimization