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):

NumberBitsModuloModulo bits
1000110001
2001020010
3001130011
4010000000
5010110001
6011020010
7011130011
8100000000
9100110001


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.


No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.