Bit Tricks with Modulo

Warning! Some information on this page is older than 5 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

Feb 2011

I like to emphasize that programming is not so similar to maths as some people say. We are used to thinking about numbers in decimal numeral system and the operations that seem most natural for us are arithmetic computations like additions, multiplication and division. On the other hand, computer works with numbers stored in binary system and bitwise operations are most efficient and natural for it. Another difference is modulo operation (the remainder after division) - a function not so frequently used in math classes, but very important in programming. That's what I'd like to talk about here.

Modulo in C++ can be done using % operator, but just as division, it is quite slow. So when doing a common operation of cycling between subsequent numbers from a limited range:

x2 = (x1 + 1) % n;

few alternatives have been developed for some special cases, using bitwise operations.

First, when the divisor is a power of 2, we can use bitwise and (operator &) to mask only least significant bits of the addition result. But this optimization can be done automatically by the compiler (at least my Visual C++ 2010).

// 7 = 0b111, so it masks 3 least significant bits.
// Equal to (x1 + 1) % 8
x2 = (x1 + 1) & 7;

When we only cycle between two values - 0 and 1 - we can use XOR (operator ^):

// Equal to (x1 + 1) % 2, for values 0, 1.
x2 = x1 ^ 1;

Finally, when we cycle between three values - 0, 1, 2 (like when indexing x, y, z components of a 3D vector), we can use the trick invented by Christer Ericson (at the end of the linked page). I came across it recently on Twitter and that's what inspired me to write this article.

// Equal to (x1 + 1) % 3, for values 0, 1, 2.
x2 = (1 << x1) & 3;

Comments | #math #c++ #algorithms Share


[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2021