Gray code

Gray code is a method of encoding a number such that each consecutive element differs only by one bit from its previous element.

For example, the integers from 0 to 7 would be represented as

0  000
1  001
2  011
3  010
4  110
5  111
6  101
7  100

Converting to Gray code

The key property to understand how to convert to and from Gray code is that Gray code is a reflected binary code.

0   0_0   0_00
-   0_1   0_01
1   ---   0_11
    1_1   0_10
    1_0   ----
          1_10
          1_11
          1_01
          1_00

Note that the digits after the underscore are “reflected” along the dashed line.

Secondly, note that the digit right after the underscore has the opposite value of what it would have in a regular binary encoding if the digit before is 1.

One algorithm, in Python, to convert to Gray code is this:

def b2g(x):
    for i in range(32):
        if (x >> (i + 1)) & 1 != 0:
            x ^= 1 << i
    return x

We can simplify this by removing the if statement:

def b2g(x):
    for i in range(32):
        # x ^= ((x >> (i + 1)) << i) & (1 << i)
        # x ^= (x >> (i + 1 - i)) & (1 << i)
        x ^= (x >> 1) & (1 << i)
    return x

Note that we are operating on just a single bit at a time. We can further simplify it by removing the loop and the mask:

def b2g(x):
    return x ^ (x >> 1)

Converting from Gray code

To convert from Gray code we simply need to reverse the operation:

def g2b(x):
    for i in range(31, -1, -1):
        if (x >> (i + 1)) & 1 != 0:
            x ^= 1 << i
    return x

Again, we can simplify it:

def g2b(x):
    for i in range(31, -1, -1):
        # x ^= ((x >> (i + 1)) << i) & (1 << i)
        # x ^= (x >> (i + 1 - i)) & (1 << i)
        x ^= (x >> 1) & (1 << i)
    return x

We cannot just remove the loop is however, since there is a dependency between each consecutive bit. We can simplify the expression inside though.

TODO work out O(log(n)) algorithm