1298. The Order Where Only One Bit Changes

Print an ordering of all 2^n values of n bits in which consecutive values differ in EXACTLY ONE bit, starting at 0. This is the Gray code order, and the one required here is the standard reflected one.

n=1 -> 0 1 n=2 -> 0 1 3 2 n=3 -> 0 1 3 2 6 7 5 4 Reading n=3 in binary: 000 001 011 010 110 111 101 100. Each step flips one bit, and the last wraps back to 000` by flipping one bit too.

## What most people try first

Building it by the recursive rule that DEFINES it, which is the right first move and is worth writing once:

G(0) = [0] G(b+1) = G(b) followed by reverse(G(b)) with bit b set

Take the previous list, append a mirrored copy, and set the new high bit throughout the second half. The mirroring is what guarantees the single-bit property across the join: the last element of the first half and the first element of the second half are the same value apart from the new bit.

That is O(2^n) work and O(2^n) memory for the intermediate lists, and it needs the list to exist before the next layer can be built.

## One expression does it directly

gray(i) = i ^ (i >> 1)

so the whole sequence is gray(0), gray(1), ..., gray(2^n - 1) with no recursion and no stored prefix.

Why it has the single-bit property. Going from i to i + 1 in ordinary binary flips a trailing run of ones to zeros and the single zero above them to a one. Say that zero sits at position p. Then i and i+1 agree above p, differ at p, and below p have all-ones against all-zeros.

Now look at i ^ (i >> 1). Bit j of the result is bit j of i XOR bit j+1 of i, which is 1 exactly where i CHANGES between adjacent positions. Between i and i+1, the only adjacent pair whose relationship changes is the one straddling position p, so exactly one bit of the Gray value changes. That is a proof rather than a pattern, and it is why no case analysis on n is needed.

## Why the order matters

An encoder that reports a position as plain binary can be read mid-transition and return a value that is neither the old nor the new one: moving from 011 to 100 changes three bits, and catching two of them gives 111 or 000. In Gray code only one bit moves at a time, so a mid-transition read gives either the old value or the new one and never a third. That is the reason the encoding exists.

## Width

n is at most 16, so values are below 65536 and both i and gray(i) fit in a signed 32-bit integer, limit 2147483647, with fifteen bits to spare. The sequence has at most 65536 entries.

JavaScript is safe with plain Numbers here, because ^ and >> coerce to signed 32 bits and every value involved already fits. #1299, which inverts this map over values to 10^18, is not like that.

Constraints - `0 ≤ n ≤ 16`