Reversing the bits in an integer x
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) <开发者_StackOverflow社区< 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?
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.
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.
精彩评论