Microsoft Interview Question
InternsCountry: India
Interview Type: Written Test
With comments:
int x = 33;
int res1 = (x & 0xAAAAAAAA) >> 1; // clear every even bit
res1 >>= 1; // shift right
int res2 = x & 0x55555555; // clear every odd bit
res2 <<= 1; // shift left
int res = res1 | res2;
System.out.println( Integer.toBinaryString(x) );
System.out.println( Integer.toBinaryString(res) );
With comments:
int x = 33;
int res1 = (x & 0xAAAAAAAA); // clear every even bit
res1 >>= 1; // shift right
int res2 = x & 0x55555555; // clear every odd bit
res2 <<= 1; // shift left
int res = res1 | res2;
System.out.println( Integer.toBinaryString(x) );
System.out.println( Integer.toBinaryString(res) );
0xAAAAAAAA is a hexadecimal number
its binary representation would be
1010 1010 1010 1010 1010 1010 1010 1010
(each A = 1010 in binary, so a total of 8 such bits)
when you do a bit wise & of this with any 32 bit number, it results in all the odd number bits masked to 0. now u RIGHT shift the result by 1 => moving the bits in even number position to odd position
similarly
0x55555555
(0101 0101 0101 0101 0101 0101 0101 0101)
when you do a bit wise & with any 32 bit number, it results in all the odd number bits masked to 0. now you LEFT shift by 1 => moving the odd number position to even number position
now you combine the result. you get the odd-even swapped result of the given number
What is the need of masking?
We can simple left shift and right and finally do OR operation.
N = (N & 0xAAAA)>>1 | (N & 0x5555)<<1
- loveCoding October 24, 2012