Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
#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
