## 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 log2(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)
{

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;

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)
{
}
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.