A Geometric Derivation of the Bitner--Ehrlich--Reingold Loopless Gray Code Algorithm
2026-08-24 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors explain how the Bitner--Ehrlich--Reingold algorithm creates a sequence known as the binary reflected Gray code by flipping bits in a specific order, called the ruler sequence. They use a geometric and tree-based approach to understand why certain pointers, called focus-pointers, are needed in the algorithm. By modeling the process with trees and stack operations, they provide a clear, step-by-step way to generate the Gray codes without extra work. Their explanation reconstructs the logic behind the algorithm but does not claim to reflect the original creators' thinking.
Gray codeBitner--Ehrlich--Reingold algorithmbinary reflected Gray coderuler sequencefocus-pointer arrayin-order traversalrecursive treesstack operationsloopless generator
Authors
Andrew Au
Abstract
The Bitner--Ehrlich--Reingold algorithm generates the binary reflected Gray code with constant work per codeword, using a focus-pointer array. Its compact update is easy to state but gives little indication of why such pointers should exist. This note reconstructs a geometric route to the algorithm. The sequence of flipped bit positions is the ruler sequence, OEIS A007814. We realize its finite prefixes as in-order traversals of recursively expanding trees, decorate each activation with its nearest ancestor to the right, contract all stack operations between successive outputs into successor jumps, and prepare the bounded level-indexed stack by predicting its future slot values. This gives and proves a branch-based loopless generator. The construction grew from an earlier informal public exposition by the author. Viewing horizontal position in the tree as time then explains each stack-slot write as a prediction for the next activation at the same level. Finally, the two possible future roles---an inherited continuation for a right child and a default continuation for a left child---are scheduled together, leading to the two assignments of the published focus-pointer algorithm. The account is a reconstructed derivation, not a claim about the historical reasoning of Bitner, Ehrlich, or Reingold.