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_{2}(*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.

### Like this:

Like Loading...

*Related*

This entry was posted on Thursday, 15 October 2009 at 23:40 and is filed under Algorithmics, C++, Cookbook. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

Saturday, 18 July 2015 at 17:19 |

I have been an embedded firmware guy for many a year but I have never seen that slick trick of dividing -1 by 3,5, etc to get the mask. How did you ever come up with that?