Fast Bit Reversal

The naïve method of reversing the bits in a number copies the bits one-by-one in a loop, or alternatively, swaps them two-by-two. This algorithms is O(n) where n is the number of bits.

However, there is an O(log n) method (when n is a power of 2); rather than taking n or n/2 steps, it takes log₂(n) steps.

This is best illustrated with simple example code (in C++). This first code fragment is for the specific case of 16-bit integers:

// *** specific bit-reverse for a word (for illustration)
uint16 bit_reverse_word (uint16 value)
{
  const uint16 mask0 = 0x5555;
  const uint16 mask1 = 0x3333;
  const uint16 mask2 = 0x0F0F;
  const uint16 mask3 = 0x00FF;

  value = (((~mask0) & value) >> 1) | ((mask0 & value) << 1);
  value = (((~mask1) & value) >> 2) | ((mask1 & value) << 2);
  value = (((~mask2) & value) >> 4) | ((mask2 & value) << 4);
  value = (((~mask3) & value) >> 8) | ((mask3 & value) << 8);

  return value;
}

Slightly more-general code follows, for up to 64 bits.

// *** perform a bit swap with automatically generated masks
inline
void masked_bit_exchange (uint64 & value, int log2_shift)
{
  const int shift = 1 << log2_shift;
  const uint64 factor = (1LL << shift) + 1;
  const uint64 mask = uint64(-1LL) / factor;

  // *** swap the masked bits with the umasked bits ***
  value = (( (~mask) & value) >> shift)
        | (( mask  & value) << shift);
}

// *** general bit-reverse a value of length (1 << log2_size) bits
uint64 bit_reverse (uint64 value, int log2_size = 6)
{
  for (int log2_shift = 0; log2_shift < log2_size; ++ log2_shift)
  {
    masked_bit_exchange (value, log2_shift);
  }
  return value;
}

This could, of course, be generalised further. However, in real code, the masks above would be better generated once at compile time, or hard-coded, rather than performing the relatively expensive arithmetic.