How does this bits reversion in a byte work?

Question

I'm new to programming and I found this method to reverse bits in a byte in C:

//(10000011) -> (11000001)

unsigned char reverse(unsigned char b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
   return b;
}

posted by an user in answer to this question, but I can't understand how it works. What do these constants mean?

Answer 1

The code first swaps the "nibbles", i.e. most significant 4 bits with least significant 4 bits. Then it swaps two top order pairs together, and bottom pairs together; finally it does pairwise swaps of 2n and 2n+1 bits.

---

I am going to denote the bits of the original value of b here by their exponent, in angle brackets (this is just a pseudo notation that I am using here, not correct C); I use o to mark any bit that is 0 always. So in the beginning we have

<76543210>

No in the first operation we have

• <76543210> & 0xF0 -> <7654oooo>
• <76543210> & 0x0F -> <oooo3210>

Now the former is shifted right by 4 bits, and the latter left by 4, thus we get

• <7654oooo> >> 4 -> <oooo7654>
• <oooo3210> << 4 -> <3210oooo>

Finally these are or'ed together, and thus after the statement

b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;

the value of b is the permutation <32107654> of the original bits.

In the second statement the mask 0xCC is 11001100 in binary, and 0x33 is 00110011 in binary; the intermediate values are:

• (<32107654> & 0xCC) >> 2 -> <32oo76oo> >> 2 -> <oo32oo76>; and
• (<32107654> & 0x33) << 2 -> <oo10oo54> << 2 -> <10oo54oo>.

These 2 or'ed together will result in permutation <10325476>. Now finally, the mask 0xAA is 10101010 in binary, and 0x55 is 01010101. Thus we have

• (<10325476> & 0xAA) >> 1 -> <1o3o5o7o> >> 1 -> <o1o3o5o7>; and
• (<10325476> & 0x55) << 1 -> <o0o2o4o6> << 1 -> <0o2o4o6o>

These or'ed together will result in permutation <01234567> which is the reverse of the original.