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

### Raunak Ramakrishnan γ»1 min read

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