# 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?

• do you know what is grey code? Commented 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. Commented Jan 26, 2014 at 12:59
• i tried to show some examples,i hope it would help you about how it is derived Commented 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 Commented 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

look also there please

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

• Sorry,i really don't understand the intuition behind the function from this answer.I can understand how that works.I just want to know why that works.? Why right shift by 1 is done ? Why it is XORed with n ,why not with any ? Etc are the questions from my side ? Commented Jan 26, 2014 at 13:30
• 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 Commented Jan 26, 2014 at 13:37
• Oh cool i understood sir ! :) Thanks a lot...Please add that in you r answer if possible. Commented Jan 26, 2014 at 13:41
• please check last link also Commented Jan 26, 2014 at 13:42
• This answer does not help how the code is working. Can someone plz explain? Commented Jan 11, 2021 at 4:27