n^(n>>1) xors each bit of
n with the bit immediately to its left. The result is a collection of bits that encode the positions where the bits of
n change from 0 to 1 or vice versa as we read them aloud from left to right.
In order to see that this produces a Gray code, we need to prove two things:
The transformation is injective, that is, we can reconstruct
n if we know
n^(n>>1). This is actually only true if we know that the first bit of
n is 0, or if our
>> operator always shifts in a zero bit at the left end even if
n is negative.
Once we know that the leftmost bits of
n is 0, it is easy to find out what
n is given
n^(n>>1) -- just start by writing down a
0, and find the rest of the bits from left to right -- each bit is the same as the previous one if the corresponding bit of
n^(n>>1) is zero, and the opposite if the corresponding bit of
n^(n>>1) is one.
Whenever we add 1 to
n, exactly one bit of
n^(n>>1) changes. Imagine adding one to
n by pencil-and-paper addition in binary. The binary representation of
n will end by a zero followed by $k$ ones (for some $k$ that might be zero). So the addition goes
where the carries stop at the point where a
0 becomes a
Now we can see that the last $k$ bits of the original
10..00, and these are still the last $k$ bits of
(n+1)^((n+1)>>1. On the other hand, the $(k+1)$th bit (corresponding to the bit position that changed from
d before, but is now the opposite of
d. And clearly no bits to the left of this position can have changed.
So, as expected, exactly one bit changes between