Part of my morning routing is to read news. One source is Google News which pointed me today to this article: Reverse Engineering an Unknown Microcontroller. While highly interesting by itself, this section struck me:

The constants 0x55, 0xAA, 0xCC, and 0x33 were staring me in the face. Could it be? Was someone stupid enough to…? Yup… These are the constants for a clever way to reverse the order of bits in a byte.

While I recognized the bit patterns (01010101, 10101010, 11001100 and 00110011) I did not know how those are used to reverse bits.

Clearly an unacceptable situation which needs to be fixed!

## Reversing Bits – Normal Way

Reversing bits is simple in C. Loop through all bits and check if they are set. If they are, set the bits in the result in reverse order (bit 0 is set, then set bit 15 in case of 16 bit integers):

```
#define BITS 16
unsigned int reverse1(unsigned int n) {
unsigned int res = 0;
for (int i = 0; i < BITS; ++i)
if (n & (1 << i))
res |= (1 << ((BITS - 1) - i));
return res;
}
```

and I always imagined the code is optimized well enough that it’s sufficiently fast. Works for all bit length too. And gcc (since v5 latest) optimizes it well (from here):

```
reverse1:
xor eax, eax
xor r8d, r8d
mov esi, 1
mov r9d, 15
.L3:
mov edx, esi
mov ecx, eax
sal edx, cl
test edx, edi
je .L2
mov ecx, r9d
mov edx, esi
sub ecx, eax
sal edx, cl
or r8d, edx
.L2:
add eax, 1
cmp eax, 16
jne .L3
mov eax, r8d
ret
```

i is in the register eax, res is r8d and n is in rdi.

## Reversing Bits – With 0xAA and 0xCC

But it turns out you can reverse bits like this too:

```
unsigned int reverse2(unsigned int n) {
n = (n & 0xAAAA) >> 1 | (n & 0x5555) << 1;
n = (n & 0xCCCC) >> 2 | (n & 0x3333) << 2;
n = (n & 0xF0F0) >> 4 | (n & 0x0F0F) << 4;
n = (n & 0xFF00) >> 8 | (n & 0x00FF) << 8;
return n;
}
```

And it’s clever how this works. Imagine a byte n with its bits named 76543210 which are the bit positions of its bits.

- The first line swaps bit pairs: you start with 76543210 and get 67452301
- The second line swaps 2 bit pairs: 45670123
- The third line swaps 4 bit pairs: 01234567, which is the reverse of where we started

Reminds me of SIMD. The fourth line swaps the top and bottom 8 bits of the 16 bit number n. Doubling the bit size is a simple extra instruction (plus double the size of the constants).

And here is the generated code (gcc v11):

```
reverse2:
mov eax, edi
shr edi
add eax, eax
and edi, 5555h
and eax, 0AAAAh
or edi, eax
mov eax, edi
sal edi, 2
shr eax, 2
and edi, 0CCCCh
and eax, 3333h
or eax, edi
mov edx, eax
sal eax, 4
shr edx, 4
and eax, 0F0F0h
and edx, 0F0Fh
or edx, eax
mov eax, edx
sal edx, 8
shr eax, 8
movzx edx, dx
or eax, edx
ret
```

Obviously way faster since there’s no loop and no branch. It is also known since 1983. I obviously never needed to reverse bits.

I guess this proves my point about learning stuff in general and in particular in IT: There’s way too much knowledge to know or learn everything. You only learn when you need it. Or when you stumble upon it accidentally.