Amazon Interview Question
Software Engineer / DevelopersOne can do this in O(1)
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) << 8));
return((x >> 16) | (x << 16));
}
My rough idea.
- majun8cn October 02, 2009A = 1;
B = 2**31 ;
for(int i=0; i<16; i++){
X = A+B ;
K = X|Input;
if(K > 0){
if(K <= B) {
Input = Input xor K;
}
}
}