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