04
04
11
Fast Modulo with 2^n Divisors
I recently had a problem in which it was required to map an integer, a, to a circle with a length equal to some power of two, N. Normally this kind of mapping is done using modular division. In fact, I found a code snippet doing just that in Jos Stam’s wonderful A Simple Fluid Solver based on the FFT.
(N + (a % N)) % N;
Wow! It works, but it’s heavy! Two modulos! But when using FFTs, the relevant sizes are almost always powers of two. So why not:
a & (N-1);
If N is a power of two, then the binary representation contains only one high bit. (N-1) effectively yields a mask with which all of the relevant lower bits of the argument, a, can be selected. Even works for negative arguments. Fast.
