Modulus With Bitwise Masks

Modulus With Bitwise Masks

Sometimes it is necessary to keep a variable with in a certain range. ex. 0 - 255, 0 - 127, etc. I will show you an easy way to do modulo base 2 numbers with bitwise masking.

First off, a little background on what modulus does. Modulus finds the remainder after division of two numbers. So the result of a % b will always be in between 0 and one less than b.

Secondly, you need to know how the bitwise AND, &, works. It will compare the corresponding bits in each term, and only set the bit in the result if both bits in each term are set.
CODE

    0101
AND 0011
  = 0001

Now that we understand modulus and binary AND lets combine the two concepts.

If the result of the modulus will always be atleast one less than the value you are dividing by then this leaves us to be able to using a bitwise mask to perform the same operation on a base 2 number. First off a bitwise mask is just a row of consecutive bits used to mask certain bits in a byte. (00001111) The masks can be located anywhere inside the byte(s) and be of any length, but for the purposes of modulo they will always start at bit 0.

Now if we where to do a modulo of 8, the result would be in the range of 0-7, 0000 - 0111 in binary. That looks like a mask right? It is and this is how we will perform the modulo. We will set up a mask of the number - 1.
CODE

16 - 15 (0x0F)
32 - 31 (0x1F)
64 - 63 (0x3F)
128 - 127 (0x7F)
256 - 255 (0xFF)

Simple example of how this works.
CODE

45 % 32
45 & 31
45 & 0x1F

    00101101 (45)
AND 00011111 (31)
  = 00001101 (13)
45 % 32 = 13

By masking of only the bits we need we can come up with a result that is within the range we need.

Now how can this be implemented.
CODE

//Lazy way
for(int i = 0, j = 0; i < 256; i++)
{
    if(j % 16 == 0) j = 0;
    else j++;
}

//Better way
for(int i = 0, j = 0; i < 256; i++)
{
    j++;
    j %= 16;
}

//Combine it into one line
for(int i = 0, j = 0; i < 256; i++)
{
    ++j %= 16;
}

//Combined using binary mask
for(int i = 0, j = 0; i < 256; i++)
{
    ++j &= 0xF;
}

By using binary operations you will improve the execution times of your algorithms significantly, as the processor can deal directly with the bits much faster than doing the division out.

Good luck and happy coding.