TIL: Gray Code: Sequential numbers, bit by bit

Let’s go over a neat thing I learned about this week.

We all know binary counting. It’s natural, we’re introduced to it around age 1 or 2, it’s delicious, and… no wait, I’m thinking about ice cream.

Focus, Christian.

Okay, so binary counting looks like this:

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101

Something you might notice is that often times you end up flipping multiple bits at once. Let’s look at the numbers 3 and 4:

3 = 011
4 = 100

3 = 011
4 = 100

We flip all 3 bits when incrementing between 3 and 4.

That’s usually not an issue, but if they can’t all be flipped at exactly the same time (say, some mechanical operation is involved and there’s the slightest of delays between each flip), you could end up with these in-between numbers that aren’t what you’d expect.

Say the bits get flipped one-by-one, left to right:

3 = 011
    111  // 7!
    110  // 6!
4 = 100

3 = 011
    111  // 7!
    110  // 6!
4 = 100

We got the garbage numbers 7 and 6 while trying to go from 3 to 4. That’s probably not great.

A solution to this is to flip only one bit when going between two numbers. And an approach to this is Gray code or “reflected binary code”. This is an alternative binary system where each number only differs by a single bit, making the above situation impossible:

Decimal  Gray Code

     0 =  000
     1 =  001
     2 =  011
     3 =  010
     4 =  110
     5 =  111
     6 =  101
     7 =  100
     8 = 1100
     9 = 1101
    10 = 1111
    11 = 1110
    12 = 1010
    13 = 1011
    14 = 1001
    15 = 1000

Decimal  Gray Code

     0 =  000
     1 =  001
     2 =  011
     3 =  010
     4 =  110
     5 =  111
     6 =  101
     7 =  100
     8 = 1100
     9 = 1101
    10 = 1111
    11 = 1110
    12 = 1010
    13 = 1011
    14 = 1001
    15 = 1000

Since there’s only ever one bit change at a time, you never risk getting a garbage value while flipping bits. Bit changes don’t have to be atomic.

There’s a few places where you may find Gray Code encodings:

• Rotary encoders
• Analog-to-Digital signal conversion
• Position sensors
• Error correction during communication
• Some genetic algorithms

I just got those from the Gray code Wikipedia page. This has tons of examples and variations and so many diagrams and animations. You can tell that the editors were really interested in this subject.

It’s pretty easy to go between decimal numbers and Gray code. Just a bit of math:

gray = value ^ (value >> 1)

gray = value ^ (value >> 1)

Though converting back takes a little more work:

mask = value
gray = value

while mask:
    mask >>= 1
    gray ^= mask

mask = value
gray = value

while mask:
    mask >>= 1
    gray ^= mask

Or, unrolled (and going up to 32 bits):

value = gray
value ^= value >> 16
value ^= value >> 8
value ^= value >> 4
value ^= value >> 2
value ^= value >> 1

value = gray
value ^= value >> 16
value ^= value >> 8
value ^= value >> 4
value ^= value >> 2
value ^= value >> 1

I’ve never looked into this before, and thought it was pretty interesting.

So that’s Gray code. What’s something new you’ve learned?