Take the 2-minute tour ×

It has come to notice that when modding

(mod(x, n))

we would prefer to make n a power of 2. How does this help and is this faster?

share|improve this question
suggested answers exploits the fact that the binary representation of an integer modular 2^k is just the trailing part of that of the integer, but be careful, it only works on unsigned integers and signed integers with 2's complement. –  kcm1700 Nov 28 '13 at 8:18
add comment

5 Answers

Your "question" is rather vague, but as a guess is this what you are looking for?

x & (n-1)

where n is a power of 2. This will give you x % n.

share|improve this answer
add comment

Envision the bits:

Let n = (1000)2 = 8

So if you want to know the remainder of X / n, you just need to know if there are any values in the 3 spots below the power of 2:

Let X = (1111)2 = 15
          ^^^ .... these will be the remainder

So if you pick some power of 2, and subtract 1 from it, you get all the bits set for anything below it:

n - 1 = (1000)2 - (0001)2 = (0111)2

Looking at X now:

  X     = (1111)2
& n - 1 = (0111)2
        = (0111)2

Since bit wise operations can be done very fast, and division operations are relatively slow, this type of modulo is much faster than doing a division.

share|improve this answer
add comment

modding by a power of 2 is an & (bitwise AND) operator.

mod(x,2^k) = x & U

where U = ((2^k)-1), which is a constant.

otherwise, you have to divide and find the remainder. bitwise AND is typically 1 clock cycle to execute, whereas divide is much slower. The details of this has to do with the logic implementation of & versus %.

share|improve this answer
add comment

To answer the question of why it is better... mod(x,y) pretty much costs as much as integer division. Much more than a simple AND operation (depending on your hardware division may cost several CPU cycles).

Slightly off topic, but definitely in an FPGA (verilog / VHDL) the AND operation results in using much much less hardware than division.

share|improve this answer
add comment

A div command in assembler (using to calculate mod) is much more expensive from shift command.

usually: 1 div = 4 shifts.

a div with power of two can be replaced by a shift.

n=2 -> shift by 1,  mod = i & 1  
n=4 -> shift by 2,  mod = i & 3

or generally for any int i

n=2^i -> shift by i, mod = x & ((2^i)-1)  
share|improve this answer
add comment

Your Answer


