Programming gems (Bit-reversed counting)

[Dan Hoey]

Several bit permutations can be achieved by shifting a subset of the bits of an
N-bit number O(N) times.  Most of the interesting ones are characterized by
moving bit I to bit R(I) where R is a function that permutes the bits of its
argument and complements some subset of those bits.  Common examples of such
permutations are reversing the bits, performing a perfect shuffle on the bits,
and--approximately--a couple of the permutations used in the DES encryption
standard.  For reversing the bits of a 32-bit number, the following code
suffices.

long BitRev(n) register long n;{

  n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa);
  n = ((n >>  2) & 0x33333333) | ((n <<  2) & 0xcccccccc);
  n = ((n >>  4) & 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0);
  n = ((n >>  8) & 0x00ff00ff) | ((n <<  8) & 0xff00ff00);
  n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);

  return n;
}