# 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:
^= 1 << i
x 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 >> 1) & (1 << i)
x 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:
^= 1 << i
x 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 >> 1) & (1 << i)
x 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