Gray code

Suppose you want to list the numbers from 0 to N in such a way that only one bit at a time changes between consecutive numbers. It’s not clear that this is even possible, but in fact it’s easy using Gray code, a method named after Frank Gray.

To convert an integer to its Gray code, take the XOR of the number with the number shifted right by 1.

    def gray(n): return n ^ n >> 1

Here’s a little Python code to demonstrate this.

    for i in range(8): print(format(gray(i), '03b'))

produces

    000
    001
    011
    010
    110
    111
    101
    100

Note that the numbers from 0 to 7 appear once, and each differs in exactly one bit from the numbers immediately above and below.

Let’s visualize the bits in Gray code with black squares for 1s and white squares for 0s.

The code that produced the plot is very brief.

    N = 4
    M = 2**N
    for i in range(N):
        for j in range(M):
            if gray(j) & 1<<i: # ith bit set
                plt.fill_between([j, j+1], i, i+1, color="k")
    plt.axes().set_aspect(1)
    plt.ylabel("Gray code bit")

The bits are numbered from least significant to most significant, starting with 1.

If you want to see the sequence carried out further, increase N. If you do, you may want to comment out the line that sets the aspect ratio to be square because otherwise your plot will be much longer than tall.

Note that the Gray code of 2ⁿ-1 is 2^n-1, i.e. it only has one bit set. So if you were to wrap the sequence around, making a cylinder, you’d only change one bit at a time while going around the cylinder.

This could make a simple classroom activity. Students could reproduce the plot above by filling in squares on graph paper, then cut out the rectangle and tape the ends together.

See the next post for how to compute the inverse Gray code.

Related posts

• Binary surprise
• Hamming codes
• De Bruijn sequences