Gray Code

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ⁿ-1 : add a 0 in front of their n-bit representation
to get the n+1 bit representation for 2ⁿ, 2ⁿ+1, 2ⁿ+2, .... 2ⁿ⁺¹-1 : add a 1 in front of the representation for 2ⁿ-1,2ⁿ-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ⁿ⁺¹-1 minus the number corresponding to the remaining n bit Gray code sequence.
(basically, split the interval 0..2ⁿ⁺¹-1 in half and count the representation in the first half in order, then count the representations in the second half in reverse order).