## Facebook Interview Question

Software Engineer Interns**Country:**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