AlgoVerse

Gray code

Order all n-bit strings so that any two neighbours differ in exactly one bit, by reflecting the previous list.

In ordinary binary counting several bits sometimes change at once (0111 → 1000). In a Gray code any two consecutive numbers differ in one bit only. It is used in rotary encoders, Karnaugh maps and the Tower of Hanoi.

Read the full explanation ↓
Input:
n=3PDF export

The 3-bit Gray code: 000, 001, 011, 010, 110, 111, 101, 100.

  1. def gray_code(n):
  2. codes = [""]
  3. for size in range(1, n + 1):
  4. reflected = codes[::-1]
  5. codes = ["0" + c for c in codes] + ["1" + c for c in reflected]
  6. rows = []
  7. for i in range(len(codes)):
  8. # The same code from the formula i XOR (i >> 1), written in n bits.
  9. formula = format(i ^ (i >> 1), "b").zfill(n) if n > 0 else ""
  10. rows.append((i, codes[i], formula))
  11. return codes

Invariant: After each reflection, codes holds every string of that length, and any two neighbours (even the last and the first) differ in one bit.

Start

codes—

The table is still empty.

Local variables

n3

Orange = changed in this step

Call stack

  1. gray_code()line 1
Step 1 of 39
Black = reflect · Orange = key stepreflect: 0/3 · row: 0/8
    Explanation

    The idea

    In ordinary binary counting several bits sometimes change at once (0111 → 1000). In a Gray code any two consecutive numbers differ in one bit only. It is used in rotary encoders, Karnaugh maps and the Tower of Hanoi.

    Building it by reflection

    1. Write the list of k-bit codes.
    2. Once with 0 in front of each code, then the list reversed with 1 in front.

    In the middle of the new list two equal codes (differing only in the first bit) meet, so the one-bit property is kept.

    A direct formula

    Code number i is i XOR (i >> 1); the last column of the table shows it, to compare with the reflection method.