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
ab..cd011..11
+00..00000..01
--------------
ab..cd100..00
where the carries stop at the point where a 0
becomes a 1
.
Now we can see that the last $k$ bits of the original n^(n>>1)
were 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 0
to 1
) was 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 n^(n>>1)
and (n+1)^((n+1)>>1
.