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.
Programming Praxis 
Function “gray2” in:
(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.
; 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…)
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:
(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!)
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 [0] P 1] (if (= i n) xs (recur (inc i) (concat xs (map #(+ P %) (reverse xs))) (+ P P)))))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:
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 = [0] for b in (1<<i for i in range(n)): gc.extend(c+b for c in reversed(gc)) return gcHere’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[1]); int k = 0; for (int i = 0; i<n; i++) { printf("%d\n", k); int r = (i+1)&~i; k ^= r; } }