Facebook Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
@Paul:
It's easy to see the cyclicity:
As a start:
1 mod 4 = 1.
1 xor 0 = 1.
Then in the 2nd step (n mod 4 = 2) you xor an even number (ie ending 0 in binary) with 1, thus it will always result in n+1.
In the third step (n mod 4 = 3) you xor a number by itself (the result was n+1 in the previous iteration), which naturally returns 0.
In the last step (n mod 4 = 0) you xor a number by 0, which results in the number itself.
Since that's even you will xor that with n+1, which is odd, the only bit difference will be the least significant, thus will result in 1 and the cycle starts over.
#define FOLD(X)\
X |= X >> 1;\
X |= X >> 2;\
X |= X >> 4;\
X |= X >> 8; \
X |= X >> 16; \
X |= X >> 32
unsigned long long XOR(unsigned long long N)
{
unsigned long long Res = 0;
unsigned long long Original = N;
if (N == 1)
{
return (1);
}
while (N > 1)
{
unsigned long long Closest = N;
FOLD(Closest);
Closest ^= Closest >> 1;
Res |= (Original - Closest + 1) % 2 ? Closest : 0;
N = N & (Closest - 1);
if (N == 0)
{
Res += (Original % 2) ? 0 : 1;
break;
}
}
return (Res);
}
c++, implementation
- kyduke October 07, 2015