## Binary Reflected Gray Code

### May 2, 2014

An *n*-bit Gray sequence is a sequence of 2^{n} values, starting from 0, in which each differs from its predecessor by a single bit. There are always 2^{n−1} *n*-bit Gray sequences; for instance, the two 2-bit Gray sequences are 0, 1, 3, 2 and 0, 2, 3, 1. It is easier to see the Gray sequences when they are written in binary; the two 2-bit Gray sequences written in binary are 00, 01, 11, 10 and 0,0 10, 11, 01, where it is clear that each element of the sequence differs from the previous one by only one bit.

Although there are many possible Gray sequences for any given number of bits, there is one Gray sequence, known as the *binary reflected gray code* BRGC, that is almost always the Gray sequence that is being discussed. Such sequences are generated recursively from the next-smaller sequence by reversing the sequence, prefixing the entries of the original sequence with a 0-bit, prefixing the entries of the reversed sequence with a 1-bit, then concatenating the two sequences. For instance, given the 2-bit Gray sequence 00, 01, 11, 10, its reversal is 10, 11, 01, 00, adding a 0-bit to the original gives 000, 001, 011, 010, adding a 1-bit to the reversal gives 110, 111, 101, 100, and concatenating the two gives 000, 001, 011, 010, 110, 111, 101, 100, which is 0, 1, 3, 2, 6, 7, 5, 4.

Your task is to write a function that generates an *n*-bit binary reflected Gray sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Function “gray2” in:

http://matthewarcus.wordpress.com/2014/04/07/ringing-the-changes/

(with m[i] = 2 for each i).

Misread at first, so I did it in binary lists rather than decimal, but it’s straight forward enough to convert.

(pfft efficiency…)

In Haskell:

Running it in ghci:

(no handling for 0-bit sequence!)

After looking into your code, I realized that I misunderstood the exercise as well: numbers ant not bit strings are required. After re-thinking my solution I boiled down all string manipulations to algebraic operations and got pretty much your solution:

A recursive version:

[sourcecodelang=”python”]

def brgc(n):

if n == 1:

return [0, 1]

else:

val = brgc(n-1)

bit = 1 << (n-1)

return val + [bit+v for v in reversed(val)]

[/sourcecode]

And an iterative version:

def brgc(n):

gc = [0]

for b in (1<<i for i in range(n)):

gc.extend(c+b for c in reversed(gc))

return gc

With proper formatting this time.

A recursive version:

And an iterative version:

Here’s another nice bit-twiddling solution – the ruler function (number of trailing 0s) for i+1 tells us which bit to flip to get the i+1th gray code: