Most Efficient Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C?

Question

What is the best algorithm to achieve the following:`0010 0000 => 0000 0100`The conversion is from MSB->LSB to LSB->MSB. All bits must be reversed; that is, this is *not* endianness-swapping.

Answer 1

Swap bits in a binary tree using bit-wise and (&), bit wise or (|), and bit shifts. This procedure is destructive to the input, so make sure to make a copy. I haven't tested this code and have not proven that it's the most efficient possible, but it should be very efficient and scale logarithmically with more bits.

//We'll name the input a.

int a = 0x00100000; //Call these bits 0xABCDEFGH

//Swap the first 4 bits with the last 4 bits

a = ((a & 0x11110000) >> 4) | ((a & 0x00001111) << 4);

/*a & 0x11110000 is 0xABCD0000, selecting the first 4 bits

(a & 0x11110000) >> 4 is 0x0000ABCD, putting the first 4 bits last

a & 0x00001111 is 0x0000EFGH, selecting the last 4 bits

and ((a & 0x00001111) << 4) is 0xEFGH0000, putting the last 4 bits first

so at the end of this line, a = 0xEFGHABCD*/

//Next swap pairs of 2 bits

a = ((a & 0x11001100) >> 2) | ((a & 0x00110011) << 2); //Now a = GHEFCDAB

//Finally, swap every other bit.

a = ((a & 0x10101010) >> 1) | ((a & 0x01010101) << 1); //Now a = HGFEDCBA

return a;