What are 0xaa and 0x55 doing?
Converting to binary,
0xaaaaaaaa == 0b10101010101010101010101010101010
0x55555555 == 0b01010101010101010101010101010101
These numbers have 0s and 1s set in alternating locations, so when you &
a number with one of these, it picks out every second bit.
If you perform the swapOddEvenBits procedure with an integer, let's say 0b01111100111101001111110000110010
, we get
0xaaaaaaaa & 0b01111100111101001111110000110010 selects the following bits:
0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 # unselected bits are 0
0x55555555 & 0b01111100111101001111110000110010 selects the following bits:
1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0
0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 gets shifted right:
0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1
and
1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 gets shifted left:
1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0
and we | the results back together:
0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1
1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0
-------------------------------
10111100111110001111110000110001
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!