2

Bit Reversal

I found this code for reversing the bits in an integer x (assume a 32bit value):

unsigned int
reverse(register unsigned int x)
{
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16));
}

I am unable to understand the logic/algorithm behind this code. What is the purpose of all the magic numbers?

AstroCB
  • 12,337
  • 20
  • 57
  • 73
user7
  • 2,339
  • 5
  • 25
  • 29
  • 2
    http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c – StuartLC Sep 19 '11 at 08:18

2 Answers2

7

Let's look at how it's done for an 8 bit value:

The first line in the function takes every second bit and moves it left or right:

12345678  -->  1-3-5-7-  -->  -1-3-5-7  -->  21436587
               -2-4-6-8       2-4-6-8-

The second line takes groups of two bits and moves left or right:

21436587  -->  21--65--  -->  --21--65  -->  43218765
               --43--87       43--87--

The third line takes groups of four bits and moves left or right:

43218765  -->  4321----  -->  ----4321  -->  87654321
               ----8765       8765----

Now the bits are reversed. For a 32 bit value you need two more steps that moves bits in groups of 8 and 16.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
  • @user639309: Then you need four steps, and 16 bit masks, like 0xaaaa and 0x5555 for the first step. If you have a 16 bit data type you can just use shift in the last step like in the code in the question, otherwise you have to mask the values like in the earlier steps. – Guffa Sep 19 '11 at 15:20
1

That's bit masks. Write them in binary form and remember how bitwise and works. You can also take a piece of paper and write down every step's masks, input and result to sort it out.

Dmitry
  • 3,069
  • 1
  • 17
  • 26