# Why does this particular algorithm work?

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?

• do you know what is grey code? Jan 26, 2014 at 12:57
• Yeah sir.If you start with 0,you have to construct sequence in such a way that previous and current term should differ only by a bit. Jan 26, 2014 at 12:59
• i tried to show some examples,i hope it would help you about how it is derived Jan 26, 2014 at 13:17

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.

• Perfect ! :D Thanks :D Jan 27, 2014 at 14:28
#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;
}


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

• why it is right shift by $1$?let us take example of $1$,which which has code $01$,now how to generate code which differ only by one integer?sure we can shift left,but this wont give answer,so in our case,this number would be $2$,or $10$,then 3 or $101$, and so on,it is just intuitive ,we know what does xor do right?by right shifting we just removing last digit ,so just tests on numbers Jan 26, 2014 at 13:37