the nth gray code

Question

the formula for calculating nth gray code is :

(n-1) XOR (floor((n-1)/2))  
(Source: wikipedia)

I encoded it as:

int gray(int n)
{
  n--;
  return n ^ (n >> 1);
}

Can someone explain how the above formula works, or possibly its deriviation?

Aurelia

I wonder if n-- is really needed here. n ^ (n>>1) is intact when codes counted from 0. – Boreas

yes, the codes are counted from 1, otherwise (n-1) in the formula would have been n. IMO, "1st gray code" makes more sense to me than "0th gray code". – Aurelia

Answer 1

If you look at binary counting sequence, you note, that neighboring codes differ at several last bits (with no holes), so if you xor them, pattern of several trailing 1's appear. Also, when you shift numbers right, xors also will be shifted right: (A xor B)>>N == A>>N xor B>>N.

    N                    N>>1                  gray
 0000           .        0000           .      0000           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0001          .         0000          .       0001          .
   || >xor = 0011           | >xor = 0001           >xor = 0010
 0010           .        0001           .      0011           .
    | >xor = 0001             >xor = 0000           >xor = 0001
 0011         .          0001         .        0010         .
  ||| >xor = 0111          || >xor = 0011           >xor = 0100
 0100                    0010                  0110

Original Xor results and shifted results differ in single bit (i marked them by dot above). This means that if you xor them, you'll get pattern with 1 bit set. So,

(A xor B) xor (A>>1 xor B>>1) == (A xor A>>1) xor (B xor B>>1) == gray (A) xor gray (B)

As xor gives us 1s in differing bits, it proves, what neighbouring codes differ only in single bit, and that's main property of Gray code we want to get.

So for completeness, whould be proven, that N can be restored from its N ^ (N>>1) value: knowing n'th bit of code we can restore n-1'th bit using xor.

A_[bit n-1] = A_[bit n] xor gray(A)_[bit n-1]

Starting from largest bit (it is xored with 0) thus we can restore whole number.

Boreas

Answer 2

Prove by induction.

Hint: The 1<<kth to (1<<(k+1))-1th values are twice the 1<<(k-1)th to (1<<k)-1th values, plus either zero or one.

Edit: That was way too confusing. What I really mean is,

gray(2*n) and gray(2*n+1) are 2*gray(n) and 2*gray(n)+1 in some order.

Cerussite

Answer 3

The Wikipedia entry you refer to explains the equation in a very circuitous manner.

However, it helps to start with this:

Therefore the coding is stable, in the sense that once a binary number appears in Gn it appears in the same position in all longer lists; so it makes sense to talk about the reflective Gray code value of a number: G(m) = the m-th reflecting Gray code, counting from 0.

In other words, Gn(m) & 2^n-1 is either Gn-1(m & 2^n-1) or ~Gn-1(m & 2^n-1). For example, G(3) & 1 is either G(1) or ~G(1). Now, we know that Gn(m) & 2^n-1 will be the reflected (bitwise inverse) if m is greater than 2^n-1.

In other words:

G(m, bits), k= 2^(bits - 1)
G(m, bits)= m>=k ? (k | ~G(m & (k - 1), bits - 1)) : G(m, bits - 1)
G(m, 1) = m

Working out the math in its entirety, you get (m ^ (m >> 1)) for the zero-based Gray code.

Rhona

Answer 4

Incrementing a number, when you look at it bitwise, flips all trailing ones to zeros and the last zero to one. That's a whole lot of bits flipped, and the purpose of Gray code is to make it exactly one. This transformation makes both numbers (before and after increment) equal on all the bits being flipped, except the highest one.

Before:

011...11
     + 1 
---------
100...00

After:

010...00
     + 1
---------
110...00
^<--------This is the only bit that differs 
          (might be flipped in both numbers by carry over from higher position)

n ^ (n >> 1) is easier to compute but it seems that only changing the trailing 011..1 to 010..0 (i.e. zeroing the whole trailing block of 1's except the highest 1) and 10..0 to 11..0 (i.e flipping the highest 0 in the trailing 0's) is enough to obtain a Gray code.

Dog