The modulo operation (% in Java) returns the remainder of a division and can be used to convert an input into a number within a fixed range.

Example modulo 4:

for (int x = 0; x < 10; x++)

{

int y = x % 4;

System.out.println(y);

}

{

int y = x % 4;

System.out.println(y);

}

Will output:

0

1

2

3

0

1

2

3

0

1

1

2

3

0

1

2

3

0

1

You can also use modulo to determine if one number is exactly divisible by another (since modulo will return a remainder of 0).

int x = 27 % 3;

System.out.println(x);

System.out.println(x);

Gives

0

Modulo is usually implemented by division which is normally the slowest hardware operation on a CPU. Imagine trying to perform modulo 3 on the number 1,000,000,000.

The most simplistic implementation of division is by loop subtraction http://en.wikipedia.org/wiki/Division_algorithm#Division_by_repeated_subtraction and the pseudocode might look something like:

long x = 1000000000L;

int mod = 3;

while(x >= mod)

{

x -= mod;

}

// remainder is x

int mod = 3;

while(x >= mod)

{

x -= mod;

}

// remainder is x

Which could take 333,333,333 loop iterations (simplistic assumption but you get the idea)

The clever optimisation is to use the bitwise AND operation which eliminates the use of loops and is a very fast CPU operation.

It requires that your modulo divisor is a power of 2 but if your code can support this then here is the method:

public int fastModulo(int dividend, int divisor)

{

return dividend & (divisor - 1);

}

{

return dividend & (divisor - 1);

}

For the example of calculating the modulo 4 result for inputs 1 to 9:

0 & (4-1) = 0

1 & (4-1) = 1

2 & (4-1) = 2

3 & (4-1) = 3

4 & (4-1) = 0

5 & (4-1) = 1

6 & (4-1) = 2

7 & (4-1) = 3

8 & (4-1) = 0

9 & (4-1) = 1

1 & (4-1) = 1

2 & (4-1) = 2

3 & (4-1) = 3

4 & (4-1) = 0

5 & (4-1) = 1

6 & (4-1) = 2

7 & (4-1) = 3

8 & (4-1) = 0

9 & (4-1) = 1

I found this idea here: http://dhruba.name/2011/07/12/performance-pattern-modulo-and-powers-of-two/

## Leave comments, ask questions, or suggest improvements