## Binary Reflected Gray Code

### May 2, 2014

An n-bit Gray sequence is a sequence of 2n values, starting from 0, in which each differs from its predecessor by a single bit. There are always 2n−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.

Pages: 1 2

### 8 Responses to “Binary Reflected Gray Code”

1. JP said

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

```; Generate a list of binary lists representing a binary reflected gray code
(define (binary-reflected-gray-code/binary-list bits)
(cond
[(zero? bits) '(())]
[else
(define rest (binary-reflected-gray-code/binary-list (- bits 1)))
(append (map (curry cons 0) rest)
(map (curry cons 1) (reverse rest)))]))

; Convert a list of binary digits to decimal
(define (binary-list->decimal ls)
(let loop ([ls ls] [acc 0])
(cond
[(null? ls) acc]
[else (loop (cdr ls) (+ (* 2 acc) (car ls)))])))

; Generate a list of n-bit decimal numbers using a binary reflected gray code
(define (binary-reflected-gray-code/decimal bits)
(map binary-list->decimal (binary-reflected-gray-code/binary-list bits)))
```

(pfft efficiency…)

2. Globules said

```import Control.Monad
import Data.Bits
import Numeric
import Text.Printf

-- The n'th BRGC.  From Warren's "Hacker's Delight", 2nd ed.
gray :: Integer -> Integer
gray n = (n `shiftR` 1) `xor` n

nBitGrays n = [gray (i-1) | i <- [1..2^n]]

printGrays n = mapM_ (printf "%0*s\n" n . base2) \$ nBitGrays n :: IO ()
where base2 n = showIntAtBase 2 ("01" !!) n ""
```

Running it in ghci:

```*Main> printGrays 3
000
001
011
010
110
111
101
100
*Main>
```
3. chmllr said
```(defn step [elems]
(let [zero-prefixed (map #(str "0" %) elems)
reversed (reverse elems)
one-prefixed (map #(str "1" %) reversed)]
(concat zero-prefixed one-prefixed)))

(defn get-BRGC [n]
(loop [i 1 elems ["0" "1"]]
(if (= i n) elems
(recur (inc i) (step elems)))))
```

(no handling for 0-bit sequence!)

4. chmllr said

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:

```(defn brgc [n]
(loop [i 0 xs  P 1]
(if (= i n) xs
(recur (inc i)
(concat xs (map #(+ P %) (reverse xs)))
(+ P P)))))
```
5. Mike said

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 = 
for b in (1<<i for i in range(n)):
gc.extend(c+b for c in reversed(gc))
return gc

6. Mike said

With proper formatting this time.

A recursive version:

```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)]
```

And an iterative version:

```def brgc(n):
gc = 
for b in (1<<i for i in range(n)):
gc.extend(c+b for c in reversed(gc))
return gc
```
7. matthew said

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:

```#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int n = 1 << atoi(argv);
int k = 0;
for (int i = 0; i<n; i++) {
printf("%d\n", k);
int r = (i+1)&~i;
k ^= r;
}
}
```