Algorithms: Gray Binary Code - A different way of ordering numbers

Gray binary code is a way of expressing binary numbers such that consecutive numbers differ in exactly 1 digit.
For example, in our conventional binary system, the numbers are

• 000
• 001
• 010
• 011
• 100
• 101
• 110
• 111 and so on

In Gray, they are:

• 000
• 001
• 011
• 010
• 110
• 111
• 101
• 100 and so on

In first system, when we go from '001' to '010', there are 2 changes namely the unit's place becomes '0' from '1' and the next digit becomes '1' from '0'.
But in Gray's system, '001' becomes '011' where there is only 1 change (that of 2nd digit).

Gray codes are used in error correction in communication.

Generating Gray codes of length n

Is there a property we can use for easily generating the Gray codes of a given length? Yes! In our previous example, we generated all the Gray codes for n=3. Ignoring the most significant bit (MSB), notice how the 4th and 5th numbers are equal in their first 2 digits, as are the 3rd and 6th, 2nd and 7th and 1st and 8th. The last 4 numbers are reflection of the first 4 if we ignore the last digit. But the last digit is 0 for the 1st 4 numbers and 1 for the last 4... We have a recursive formulation.

R(0) = []
R(n+1) = 0R(n) + 1R'(n) (R'(n) = reverse of R(n))
For n=0, we have an empty list.
For n+1, we take R(n), prepend 0 to all elements and to this sequence, we add reverse of R(n) prepended with 1.

This can be succinctly expressed in Python as:

def gray_code(n):
    if n <= 0:
        return []
    if n == 1:
        return ['0', '1']
    res = gray_code(n-1)
    return ['0'+s for s in res] + ['1'+s for s in res[::-1]]

The above function returns in correct order all the 2^n Gray codes of length n.
We had to add a case for n==1 because we are treating the numbers as strings so we can prepend '0' or '1'. As n=0 is an empty list, we need another case where we first add the strings.

Converting a binary number to Gray code

How do we convert a binary number to Gray code e.g what is Gray code equivalent of 7 (111 in binary)? From our earlier example, it is 100 = 4. So we need a function which takes an integer and returns the equivalent Gray code as integer.

We can use our recursive formulation from earlier to arrive at an algorithm. Let n = 2^a + b. Here, a is the MSB of n. G(n) is the Gray code of n. From our earlier formula, G(n) = 2^a + G(2^a-1-b) .. because of the reflection property. Thus, we know the value of G(n) at ath digit. We can keep iterating to get the other digits of G(n).

Our pseudo-code:

def bin_to_gray(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    a = MSB(n) # Assume MSB function exists. It finds most significant bit of n
    b = n - 2**a
    return 2**a + bin_to_gray(2**a-1-b)

from math import log2 as l2
# A simple way to find MSB
def MSB(n):
    return int(l2(n))

An even faster way:

It turns out that there is an even faster way of getting the nth Gray code from n.
G(n) = n xor n/2

In C, Java or Python, this is expressed as:

return n ^ (n >> 1)

Addendum : Generating all Gray codes Knuth style!

The legendary Donald Knuth uses this algorithm to generate all the tuples in his Art of Computer Programming Vol 4A:

public static void gen_gray_bin_taocp(int n) {
    boolean p = false; // parity bit
    byte[] a = new byte[n]; // each bit is an element in this array
    int j = 0;
    while (true) {
        System.out.println(Arrays.toString(a)); // Will print the number in reverse order
        p = !p;
        if (p)
            j = 0;
        else {
            j = 1;
            // Find min j so that a[j-1] = 1
            while (j < n) {
                if (a[j-1] == 1)
                    break;
                j++;
                if (j == n) // Termination condition
                    return;
        }
        a[j] = (byte) (1-a[j]); // We flip the element at j
    }
}