Published by Dimitris Kougioumtzis · Updated
Map each binary index i to i XOR (i >> 1); adjacent codes differ by one bit.
Reflect the current sequence and set a new high bit on the reflected half, covering all codes with one-bit consecutive changes.
When to use Binary reflected Gray code
State ordering with single-bit transitions.
Choosing an alternative
Ordinary binary counting can flip several bits at a carry.
Worked example: input and state changes
Example input
3
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Gray-code sequence starts empty.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 8, "bits": 3 }Step 2: Index 001 → Gray code 001.
State at this checkpoint
{ "values": [ 0, 1, 0, 0, 0, 0, 0, 0 ], "active": [ 1 ], "kind": "matrix", "columns": 8, "bits": 3 }Step 5: Index 100 → Gray code 110.
State at this checkpoint
{ "values": [ 0, 1, 3, 2, 6, 0, 0, 0 ], "active": [ 4 ], "kind": "matrix", "columns": 8, "bits": 3 }Step 7: Index 110 → Gray code 101.
State at this checkpoint
{ "values": [ 0, 1, 3, 2, 6, 7, 5, 0 ], "active": [ 6 ], "kind": "matrix", "columns": 8, "bits": 3 }Step 9: Gray-code sequence complete: 8 codes.
State at this checkpoint
{ "values": [ 0, 1, 3, 2, 6, 7, 5, 4 ], "active": [], "kind": "matrix", "columns": 8, "bits": 3 }
Expected final state
Gray-code sequence complete: 8 codes.
Complexity and input bounds
Family: Number theory. Time complexity: O(2^bits).
Space complexity: O(2 to the bits) output storage.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
One bit count from 1 to 8. Codes are shown as decimal integers.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Gray-code values are not in numeric order, and generating all codes requires exponential output.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 | // bits from 1 to 8. Writes 2^bits decimal Gray codes and returns count. Output needs capacity 2^bits. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(bits, output) { let count = 1 << bits; for (let i = 0; i < count; i++) { output[i] = i ^ (i >> 1); } return count; } |
Source
Gray's original pulse-code patent is a historical primary source, not a journal paper.
- Pulse code communication (US2632058A)
Frank Gray (1953). Original patent.