binary Gray code

An $n$ -bit binary Gray code is a non-repeating sequence of the integers from $0$ to $2^{n}-1$ inclusive such that the binary representation of each number in the sequence differs by exactly one bit from the binary representation of the previous number: that is, the Hamming distance between consecutive elements is $1$ . In addition, we also define a cyclic Gray code to be a Gray code where an extra condition is imposed: The last number in the sequence must differ by exactly one bit from the first number in the sequence.

For example, one $3$ -bit cyclic Gray code is:

000_{2}

010_{2}

011_{2}

001_{2}

101_{2}

111_{2}

110_{2}

100_{2}

There is a one-to-one correspondence between all possible $n$ -bit Gray codes and all possible Hamiltonian cycles on an $n$ -dimensional hypercube. (To see why this is so, imagine assigning a binary number to each vertex of a hypercube where an edge joins each pair of vertices that differ by exactly one bit.)