Why does this particular algorithm work?

Question

I was reading about gray codes. There I found this algorithm.

int g (int n) 
{
    return n ^ (n >> 1);
}

Given a number $n$, this finds the $n$th gray code.

Suppose if $n=10$, the answer would be $1111$. Since $n=10(1010)$, $$\begin{align} n>>1 &= 0101 \\ n \wedge (n>>1) &= 1111. \end{align}$$

I can understand the working. But I don't really understand how they derived this? I mean can somebody give me the intuition behind this?

Answer 1

#include<iostream>

    using namespace std;

    int g(int n)
    { 
     return  n^(n>>1);
    }

    int main()
    {
    int n=10;
    cout<<g(n)<<endl;

    return 0;
    }

yes you are right answer is $15=1111$

the main point is that ^ mark is xor,which means that Exclusive disjunction or exclusive oris a logical operation that outputs true whenever both inputs differ (one is true, the other is false)

there is time table for it

XOR Truth Table
  Input     Output
A   B
0   0   0
0   1   1
1   0   1
1   1   0

now >> symbol means simple divide by $2$,in your case $10/2=5$ or $0101$

now we have

$1010$ xor $(0101)$=$1111$

for generally let us find grey codes from 0 to n

#include<iostream>

    using namespace std;

    int g(int n)
    { 
     return  n^(n>>1);
    }

    int main()
    {
    for (int n=0;n<=10;n++){
    cout<<g(n)<<endl;

}
    return 0;
    }

answer http://codepad.org/xAMnNA0r

Actually ^ mark shows true at this places where this two sequence differ from each other,which of course is basic idea behind of grey code additional information you can check there

http://mathworld.wolfram.com/GrayCode.html

look also there please

http://www.most.gov.mm/techuni/media/BinaryToGrayCodeConverter.pdf

Answer 2

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.