What do 0xaa and 0x55 do?
I tried Googling but couldn't find anything clear @. @ ... Can anyone explain in non-professional terms what is going on in this code?
This is a problem from the book "Cracking Coding Interviews".
"Write a program to exchange odd and even bits into an integer with as many instructions as possible (for example, bit 0 and bit 1 are swapped, bit 2 and 3 are swapped, etc.).
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 understand it ... (doesn't help so that it isn't in Python):
int swapOddEvenBits(int x) {
return ( ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1) );
source to share
Let's break it down.
return ( ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1) );
Let's consider first (x & 0xaaaaaaaa)
. If you break down 0xaaaaaaaa
to the bit level, you get 1010 1010 1010 1010 1010 1010 1010 1010
(as a
, in binary, 1010
). So, (x & 0xaaaaaaaa)
says, return only all marked 1
in x
. This is called bit masking. Then you shift it one place - this is how you change place with even numbers (so now the second bit takes the place of the first bit, and the fourth takes the place of the third, etc.).
You do the same thing with (x & 0x55555555)
- if you add it to the bit level, you get 0101 0101 0101 0101 0101 0101 0101 0101
(as 5
, in binary, 0101
). This masks all the even bits in x
and gives you all the odd bits. Then you shift all the bits remaining to 1. Finally, you use the or
( |
) operator to concatenate the two bit sequences and your answer.
Example: Take 2456086205. We convert this to binary and get 1001 0010 0110 0100 1110 0110 1011 1101
. Now we do (x & 0xaaaaaaaa)
and receive
1001 0010 0110 0100 1110 0110 1011 1101 & 1010 1010 1010 1010 1010 1010 1010 1010
,
which is 1000 0010 0010 0000 1010 0010 1010 1000
. Slide it to the right and get it 0100 0001 0001 0000 0101 0001 0101 0100
.
Now let's do (x & 0x55555555)
and get
1001 0010 0110 0100 1110 0110 1011 1101 & 0101 0101 0101 0101 0101 0101 0101 0101
,
what is equal 0001 0000 0100 0100 0100 0100 0001 0101
. Slide this to the left and you have 0010 0000 1000 1000 1000 1000 0010 1010
.
Finally, we comply 0100 0001 0001 0000 0101 0001 0101 0100 | 0010 0000 1000 1000 1000 1000 0010 1010
. Then we get 0110 0001 1001 1000 1101 1001 0111 1110
, which, as you can see, is the solution!
source to share
Conversion to binary,
0xaaaaaaaa == 0b10101010101010101010101010101010
0x55555555 == 0b01010101010101010101010101010101
These numbers contain 0s and 1s given in different places, so when you &
number with one of them, it fetches every other bit.
If you run swapOddEvenBits 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
source to share
We know that 0xaa and 0x55 are hexadecimal representation. Moreover, each character in hexadecimal format is represented using 4 bits
So 0xaa is equivalent to 1010 1010 (since, a = 1010 in binary) and 0x55 is equivalent to 0101 0101 (since 5 = 0101 in binary)
Anding any number with them will return us the alternate bits of the number and therefore useful in solving problems such as exchanging odd and even numbers.
source to share