Dense Gray codes, or easy ways to generate cyclic and non-cyclic Gray codes for the first n whole numbers

摘要

The standard binary reflected Gray code gives a sequence of binary numbers in the range 0 to n - 1, where n is a power of 2, such that each number in the sequence differs from the preceding number in only one bit. We present two methods to compute Gray codes containing exactly n numbers in the range 0 to n - 1-that is, a permutation of 〈0, 1, ..., n - 1〉 in which each number differs from the preceding number in only one bit-where n is unconstrained. The first method produces a Gray code that is not cyclic: the first and last numbers in the sequence differ in more than one bit. The second method produces a cyclic Gray code if n is even, so that the first and last numbers differ in only one bit, at the expense of a slightly more complicated procedure. Both methods are based on the standard binary reflected Gray code and, as in the binary reflected Gray code, each number in the output sequence can be computed in a constant number of word operations given just its index in the sequence.