Why does this particular algorithm work? 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?
 A: 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.
A: #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
