## Binary Reflected Gray Code

### May 2, 2014

This is a simple recursion on sequences represented as lists, with the sequence (0) as the recursive base:

```(define (gray n)
(define (add x) (lambda (y) (+ x y)))
(let loop ((n n) (g 1) (gs (list 0)))
(if (zero? n) gs
(loop (- n 1) (+ g g)
(append gs (map (add g) (reverse gs)))))))
```

The magic is in the last line. The next-smaller sequence is in variable gs, which is reversed, then the next-larger power-of-two, which is accumulated in variable g, is added to each item of the reversed sequence, and finally the two lists are appended. The `add` function is a curried form of addition. Here are the first several Gray sequences:

```> (gray 0)
(0)
> (gray 1)
(0 1)
> (gray 2)
(0 1 3 2)
> (gray 3)
(0 1 3 2 6 7 5 4)
> (gray 4)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8)
> (gray 5)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29
28 20 21 23 22 18 19 17 16)
> (gray 6)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29
28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63
62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33
32)
> (gray 7)
(0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29
28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63
62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33
32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105
104 120 121 123 122 126 127 125 124 116 117 119 118 114 115
113 112 80 81 83 82 86 87 85 84 92 93 95 94 90 91 89 88 72
73 75 74 78 79 77 76 68 69 71 70 66 67 65 64)
```

Since the n-bit Gray sequence is embedded in the first half of the n+1-bit Gray sequence, it makes sense to talk about the kth element of the binary reflected Gray sequence, irrespective of the bit length. The kth element of the Gray sequence is k ⊕ ⌊k / 2⌋,where ⊕ is the logical `xor` operator, which can be expressed simply in C as `(k >> 1) ^ k`. Thus, here is another way to write the n-bit gray sequence:

```(define (nth-gray n) (bitwise-xor n (ash n -1)))

(define (gray n)
(do ((k 0 (+ k 1)) (gs (list) (cons (nth-gray k) gs)))
((= k (expt 2 n)) (reverse gs))))

> (nth-gray 0)
0
> (nth-gray 1)
1
> (nth-gray 2)
3
> (nth-gray 3)
2
> (nth-gray 4)
6
> (nth-gray 5)
7
> (nth-gray 6)
5
> (nth-gray 7)
4
```

You can run the program at http://programmingpraxis.codepad.org/ndutMKZE.

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

In Haskell:

```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;
}
}
```