2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ do you know what is grey code? $\endgroup$ Jan 26, 2014 at 12:57
  • $\begingroup$ 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. $\endgroup$
    – vaidy_mit
    Jan 26, 2014 at 12:59
  • $\begingroup$ i tried to show some examples,i hope it would help you about how it is derived $\endgroup$ Jan 26, 2014 at 13:17

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perfect ! :D Thanks :D $\endgroup$
    – vaidy_mit
    Jan 27, 2014 at 14:28
1
$\begingroup$
#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

$\endgroup$
5
  • $\begingroup$ 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 ? $\endgroup$
    – vaidy_mit
    Jan 26, 2014 at 13:30
  • $\begingroup$ 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 $\endgroup$ Jan 26, 2014 at 13:37
  • $\begingroup$ Oh cool i understood sir ! :) Thanks a lot...Please add that in you r answer if possible. $\endgroup$
    – vaidy_mit
    Jan 26, 2014 at 13:41
  • $\begingroup$ please check last link also $\endgroup$ Jan 26, 2014 at 13:42
  • $\begingroup$ This answer does not help how the code is working. Can someone plz explain? $\endgroup$ Jan 11, 2021 at 4:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .