Gray codes: counting one bit at a time

Lists the reflected binary Gray code, checks that neighbouring codes differ in exactly one bit, and compares the number of bit flips needed to count through all n-bit words with ordinary binary counting.

import matplotlib.pyplot as plt
import numpy as np

from mathematicskit.combinatorics import gray_code

The 4-bit reflected Gray code

codes = gray_code(4)
for k, g in enumerate(codes):
    print(f"{k:2d}: binary {k:04b}  gray {g:04b}")

 0: binary 0000  gray 0000
 1: binary 0001  gray 0001
 2: binary 0010  gray 0011
 3: binary 0011  gray 0010
 4: binary 0100  gray 0110
 5: binary 0101  gray 0111
 6: binary 0110  gray 0101
 7: binary 0111  gray 0100
 8: binary 1000  gray 1100
 9: binary 1001  gray 1101
10: binary 1010  gray 1111
11: binary 1011  gray 1110
12: binary 1100  gray 1010
13: binary 1101  gray 1011
14: binary 1110  gray 1001
15: binary 1111  gray 1000

As a picture: one column changes per row

bits = np.array([[(g >> (3 - b)) & 1 for b in range(4)] for g in codes])
fig, ax = plt.subplots(figsize=(3, 6))
ax.imshow(bits, cmap="Greys", aspect="auto")
ax.set_xlabel("bit")
ax.set_ylabel("step")
ax.set_title("4-bit Gray code")

Text(0.5, 1.0, '4-bit Gray code')

Bit flips to count through every word

for n in range(2, 9):
    binary_flips = sum(bin(k ^ (k + 1)).count("1") for k in range(2**n - 1))
    gray = gray_code(n)
    gray_flips = sum(bin(a ^ b).count("1") for a, b in zip(gray, gray[1:]))
    print(f"n = {n}: binary counting flips {binary_flips} bits, Gray code flips {gray_flips}")

n = 2: binary counting flips 4 bits, Gray code flips 3
n = 3: binary counting flips 11 bits, Gray code flips 7
n = 4: binary counting flips 26 bits, Gray code flips 15
n = 5: binary counting flips 57 bits, Gray code flips 31
n = 6: binary counting flips 120 bits, Gray code flips 63
n = 7: binary counting flips 247 bits, Gray code flips 127
n = 8: binary counting flips 502 bits, Gray code flips 255