The definition of the Gray Code requires that the representation of 2 succesive numbers must differ by exactly one bit. You can get this kind of representation with the following construction:

0 is represented with 0

1 is represented with 1.

To get the representations of 2,3 : add a 1 in front of the representations
of 1,0:

2 : add 1 in front of 1 ( 1 1 )

3 : add 1 in front of 0 ( 1 0 )

To get the representation of 4,5,6,7: add 1 in front of the representations
for 3,2,1,0:

4 : 1 in front of 3 ( 1 10 )

5 : 1 in front of 2 ( 1 11 )

6 : 1 in front of 1 ( 1 01 )

7 : 1 in front of 0 ( 1 00 )

To get the n+1 bit representation for 0,1,...2^{n}-1 : add a 0
in front of their n-bit representation

to get the n+1 bit representation for 2^{n}, 2^{n}+1, 2^{n}+2,
.... 2^{n+1}-1 : add a 1 in front of the representation for 2^{n}-1,2^{n}-2,....1,0

To get the number corresponding to a particular n+1 bit Gray code represetation,
do the following:

If the most semnificative bit is 0, throw it away and return the number
corresponding to the remaining n bits

If it is 1, return 2^{n+1}-1 minus the number corresponding to
the remaining n bit Gray code sequence.

(basically, split the interval 0..2^{n+1}-1 in half and count the
representation in the first half in order, then count the representations
in the second half in reverse order).

RETURN TO PREVIOUS PAGE