Bit reversal

n-bit-reverse.c

/*
 Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division)
*/

unsigned char b; // reverse this (8-bit) byte 
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;


/*
 Reverse an N-bit quantity in parallel in 5 * lg(N) operations
*/


unsigned int v; // 32-bit word to reverse bit order

// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);