Gray code

Gray code is a binary numeral system where two successive values differ in only one bit.

For example, the sequence of Gray codes for 3-bit numbers is: 000, 001, 011, 010, 110, 111, 101, 100, so $G(4) = 6$.

This code was invented by Frank Gray in 1953.

Finding Gray code

Let's look at the bits of number $n$ and the bits of number $G(n)$. Notice that $i$-th bit of $G(n)$ equals 1 only when $i$-th bit of $n$ equals 1 and $i + 1$-th bit equals 0 or the other way around ($i$-th bit equals 0 and $i + 1$-th bit equals 1). Thus, $G(n) = n \oplus (n >> 1)$:

  int g (int n) { 
      return n ^ (n >> 1); 
  }

Finding inverse Gray code

Given Gray code $g$, restore the original number $n$.

We will move from the most significant bits to the least significant ones (the least significant bit has index 1 and the most significant bit has index $k$). The relation between the bits $n_i$ of number $n$ and the bits $g_i$ of number $g$:

$n_k = g_k$,
$n_{k-1} = g_{k-1} \oplus n_k = g_k \oplus g_{k-1}$,
$n_{k-2} = g_{k-2} \oplus n_{k-1} = g_k \oplus g_{k-1} \oplus g_{k-2}$,
$n_{k-3} = g_{k-3} \oplus n_{k-2} = g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3}$,
$...$

The easiest way to write it in code is:

  int rev_g (int g) {
    int n = 0;
    for (; g; g >>= 1)
      n ^= g;
    return n;
  }

Practical applications

Gray codes have some useful applications, sometimes quite unexpected:

Practice Problems