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?

This swaps groups of 4 bits with each other, then 2, then 1. So first, bits 7654 with 3210. Then, 7632 with 5410. Then, 7531 with 6420. Just writing this made me realise that it's not easy to explain without pointing :P — AntonH, Mar 17 '17 at 20:58
Step through the function in a debugger, printing `b` in binary after each statement. You will then be enlightened. — Barmar, Mar 17 '17 at 20:59

score 5 · Answer 1 · answered Mar 17 '17 at 21:02

It might help to look at the binary representation of the above numbers:

0xF0: 11110000
0x0F: 00001111

0xCC: 11001100
0x33: 00110011

0xAA: 10101010
0x55: 01010101

The first pair of numbers are used to mask out and swap the first 4 bits and the last 4 bits of a byte.

The second pair masks out and swaps the first 2 bits and last 2 bits of a set of 4 bits.

The third pair masks out and swap adjacent pairs of bits.

Antti Haapala -- Слава Україні · Accepted Answer · 2017-03-17T21:22:50.377

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.

AntonH · Answer 3 · 2017-03-17T21:11:26.300

So it's just a lot of bit shifting. The bits are in the following order:

76543210

Now, first line, first part keeps high bits, sets lower bits to 0 (mask is 0b11110000), shifts them 4 to the right. Second part does the same for the lower bits (mask is 0b00001111), and shifts to the left:

first line, first part:  7654xxxx => xxxx7654 (bits shift to the right)
first line, second part: xxxx3210 => 3210xxxx (bits shift to the left)
add them together:                => 32107654

Then, second line. Same action, different masks (0b11001100 and 0b00110011, respectively), with 32107654:

second line, first part:  32xx76xx => xx32xx76 (bits shift to the right)
second line, second part: xx10xx54 => 10xx54xx (bits shift to the left)
add them together:                 => 10325476

Third line is the same with a again other masks(0b10101010 and 0b01010101, respectively), with 10325476:

third line, first part:  1x3x5x7x => x1x3x5x7 (bits shift to the right)
third line, second part: x0x2x4x6 => 0x2x4x6x (bits shift to the left)
add them together:                => 01234567

So we end up, finally, with the action:

76543210 => 01234567

score 0 · Answer 4 · answered Mar 17 '17 at 21:06

Let's number the bits in b as follows:

01234567

0xF0 in binary is 11110000, and 0x0F is 00001111. The first assignment shifts the leftmost 4 bits to the right, and the rightmost 4 bits to the left, then combines them with OR, so the result is:

45670123

0xCC is 11001100, and 0x33 is 00110011. When these masked bits are shifted by 2 bits and combined, the result is:

67452301

Finally, 0xAA is 10101010 and 0x55 is 01010101. When these masks and shifts are done, the result is:

76543210

Voila! this is the reversed order.

Notice that for each pair of shifts, the bit masks are inverses of each other, and the number of bits being shifted are the same as the length of the sequences of 1 bits in the mask. So each of them is swapping groups of bits whose size is that sequence length.

score 0 · Answer 5 · answered Apr 06 '17 at 11:19

You need to understand 4 main things in order to understand what above code means.

& (AND) Bitwise Operator.
| (OR) Bitwise Operator.
>> (Right Shift Operator).
<< (Left Shift Operator).

Luckily, I just have written a detailed blog that explains everything about Number System and Bit Manipulation

How does this bits reversion in a byte work?

5 Answers5