What are 0xaa and 0x55 doing?

Question

I tried Googling, but couldn't find anything comprehensible @.@ ... Could someone please explain in layman's terms what is happening in this code?

It's a problem from the book "Cracking the Coding Interview".

"Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and 3 are swapped, and so on)."

The way I did it didn't involve bit manipulation because I couldn't figure out how %\ ...

def swap(n):

    b = bin(n)[2:]
    print(b)
    if len(b)%2 != 0:
        c = True
        b = b[0] + b

    pairs = wrap(b, 2)
    pairs = [i[::-1] for i in pairs]
    ans = ''.join(pairs)

    if c: ans = ans[1:]
    print(ans)

But now I'm looking at their answer and I don't really get it... (doesn't help that it's not in Python) :

int swapOddEvenBits(int x) {
  return ( ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1) );

Answer 1

Let's break this down.

return ( ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1) );

First, we'll look at (x & 0xaaaaaaaa). If you break 0xaaaaaaaa down to the bit level, you end up with 1010 1010 1010 1010 1010 1010 1010 1010 (as a, in binary, is 1010). So (x & 0xaaaaaaaa) is saying, return only every even-placed 1 in x. This is called bit masking. Then, you right shift it by one place - this is how you make the even numbers switch place (so now the second bit occupies the place of the first bit, and the fourth the third, etc).

You do the same thing with (x & 0x55555555) - if you break it down to the bit level, you end up with 0101 0101 0101 0101 0101 0101 0101 0101 (as 5, in binary, is 0101). This masks all the even-placed bits in x, and gives you all the odd-placed bits. Then, you shift all bits left by 1. Finally, you use the or (|) operator to combine the two bit-sequences, and that's your answer.

Example: Let's take 2456086205. We convert that into binary and get 1001 0010 0110 0100 1110 0110 1011 1101. Now, we do (x & 0xaaaaaaaa), and get

1001 0010 0110 0100 1110 0110 1011 1101 & 1010 1010 1010 1010 1010 1010 1010 1010,

which equals 1000 0010 0010 0000 1010 0010 1010 1000. Shift this to the right and you get 0100 0001 0001 0000 0101 0001 0101 0100.

Now, do (x & 0x55555555), and get

1001 0010 0110 0100 1110 0110 1011 1101 & 0101 0101 0101 0101 0101 0101 0101 0101,

which equals 0001 0000 0100 0100 0100 0100 0001 0101. Shift this to the left and you get 0010 0000 1000 1000 1000 1000 0010 1010.

Finally, we do 0100 0001 0001 0000 0101 0001 0101 0100 | 0010 0000 1000 1000 1000 1000 0010 1010. We then get 0110 0001 1001 1000 1101 1001 0111 1110, which, as you can see, is the the solution!