How does this code work to reverse bits in number?

Question

unsigned reverse_bits(unsigned input)
{  
     //works on 32-bit machine  
     input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;
     input = (input & 0x33333333) <<  2 | (input & 0xCCCCCCCC) >>  2;
     input = (input & 0x0F0F0F0F) <<  4 | (input & 0xF0F0F0F0) >>  4;
     input = (input & 0x00FF00FF) <<  8 | (input & 0xFF00FF00) >>  8;
     input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;

      return input;
}

how does this work?

Answer 1

Suppose I have a hand of 8 cards:

7 8 9 10 J Q K A

How can we reverse them? One way is to swap adjacent pairs:

8 7 10 9 Q J A K

Then, swap adjacent groups of 2: exchange 8 7 and 10 9, etc:

10 9 8 7 A K Q J

Finally, exchange groups of four, which is half the size of 8:

A K Q J 10 9 8 7

Done.

You can do this in different orders. Why? Because the exchanges are stable with respect to each other. When we exchange the upper half of the cards with the lower half, for instance, the pairs stay in the same order. Or when we exchange pairs, the halves stay in the same order.

This is what the code is doing with the bit operations. For instance to swap pairs we can use the mask 01010101 to pick out the even bits, and 10101010 to pick out the odd bits, using the bitwise AND operation:

  ABCDEFGH     ABCDEFGH
& 01010101   & 10101010
----------   ----------
= 0B0D0F0H     A0C0E0G0

Remember, the rule for and is that given some bit value X, X & 1 = X and X & 0 = 0. The 1 bits in the mask preserve the value, and the 0 bits in the mask produce 0. This is called masking because it looks exactly like a mask used in spray-painting, etc. The 1 bits "cover" the places you don't want to "paint" with zero.

Next, the left result is shifted left one bit, and the right result shifted right. This brings about the swap:

  B0D0F0H0     0A0C0E0G

Finaly, the two are combined with logical OR. The rule for OR is that X or 0 is X. The two parts each have 0 where the other has nonzero, and so the bits simply merge:

  B0D0F0H0
| 0A0C0E0G
----------
= BADCFEHG

And now the pairs are swapped.

Answer 2

It can be understood by induction.

Start with the base case, a two bit number

input = (input & 0x1) <<  1 | (input & 0x2) >>  1;

Now progress to a four bit number

input = (input & 0x5) <<  1 | (input & 0xA) >>  1; // swap bits
input = (input & 0x3) <<  2 | (input & 0xc) >>  2; // swap bit pairs

Progress to an 8 bit number

input = (input & 0x55) <<  1 | (input & 0xAA) >>  1; // swap bits
input = (input & 0x33) <<  2 | (input & 0xCC) >>  2; // swap bit pairs
input = (input & 0x0F) <<  4 | (input & 0xF0) >>  4; // swap bit nibbles

and so on.