## 23/10/2017

### [Java] Calculate modulus of a number and a power of two

More bit magic!

This time we will efficiently compute the modulus of a number and a power of two. If you write down a couple sample cases you immediately spot the trick; let's use N mod 4 (0100):

 Number Bits Modulo Modulo bits 1 0001 1 0001 2 0010 2 0010 3 0011 3 0011 4 0100 0 0000 5 0101 1 0001 6 0110 2 0010 7 0111 3 0011 8 1000 0 0000 9 1001 1 0001

The red bit is the only set bit in our modulus, the bold bits in both the number and the result are always matching.. interesting.
We now have a very easy way of calculating the result by always returning all the bits in the number that appear after the modulo bit:

n & (mod - 1)

We already saw previously that n - 1 will provide us with a mask where all the bits after the first set LSB are set to 1. We can then AND this with the number itself to erase everything that appears before, and including, the modulo bit and return only what's right of it.

You can check more bit magic on my Gist along with some test cases.