1299. Recovering the Index From a Gray Code Value
Given a Gray code value g, print the index i it came from, where
g = i XOR (i >> 1) as in problem 1298. Answer q such queries.
0 -> 0
1 -> 1
3 -> 2
2 -> 3
6 -> 4
## What most people try first
Searching: generate gray(i) for i = 0, 1, 2, ... until it equals g. That
is correct and O(g) per query, which at g = 10^18 cannot run.
The next instinct, g ^ (g >> 1), is wrong. The Gray map is not its own
inverse. On g = 3 it gives 3 ^ 1 = 2, which happens to be right, and on
g = 6 it gives 6 ^ 3 = 5, where the answer is 4. One coincidence and then a
wrong answer is the usual pattern with self-inverse guesses.
## Fold the value onto itself
The forward map says bit j of g is bit j of i XOR bit j+1 of i. So
reading from the TOP downward, where there is nothing above:
bit of i at the top = bit of g at the top
bit of i at j = bit of g at j XOR bit of i at j+1
which unrolls into "bit j of i is the XOR of all bits of g from j
upward". That running XOR from the top is exactly what repeated folding
computes:
x = g
x ^= x >> 1
x ^= x >> 2
x ^= x >> 4
x ^= x >> 8
x ^= x >> 16
x ^= x >> 32
After the first line each bit holds the XOR of two bits of g; after the second,
of four; and so on, doubling each time, so six lines cover 64 positions. The
doubling works because XOR is associative and each bit is its own inverse, so
combining two already-folded halves never double-counts a bit: a bit XORed in
twice cancels, and the shifts are chosen so that cannot happen.
## Checking it
g = 6 = 110. Fold: 110 ^ 011 = 101; then 101 ^ 001 = 100 = 4. And
gray(4) = 4 ^ 2 = 6. Correct.
The forward and backward maps are a bijection on every fixed width, which is
why #1298's sequence is a permutation of all 2^n values. A useful self-check
on any implementation is to apply both and get back where you started; the
oracle for this block does exactly that on every case.
## Width
g reaches 10^18, below 2^60. The ANSWER can be larger than g: for
g = 2^59 the index is 2^60 - 1 = 1152921504606846975, since the Gray value
of a solid run of ones is a single high bit. So both input and output need a
64-bit integer, whose limit is 9223372036854775807, and a signed 32-bit
integer, limit 2147483647, cannot hold either.
The x >> 32 line is the one that silently vanishes in a 32-bit type, which is
how a 32-bit implementation of this is correct for small values and wrong for
large ones. In JavaScript all six shifts coerce to signed 32 bits, so the
reference uses BigInt.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ g ≤ 1000000000000000000` - the answer always fits in a signed 64-bit integer
Input
The first line contains an integer q.
Each of the next q lines contains one integer g.
Output
For each value print one integer on its own line: the index i with i XOR (i >> 1) equal to g.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.