Gray Code Decode

Convert a binary-reflected Gray code integer back to its standard binary representation.

gray-code bit-manipulation xor integers

Write a function `gray_decode(n: int) -> int` that takes a non-negative integer `n` which represents a value encoded in binary-reflected Gray code, and returns the standard binary integer it corresponds to.

The decoding rule is: the most significant bit (MSB) of the result equals the MSB of the Gray code. For each subsequent bit, the result bit is the XOR of the current Gray code bit and the previous result bit. In integer terms, you can repeatedly XOR the Gray code value with itself shifted right by 1, 2, 4, 8, ... until the shift exceeds the bit length.

For example, the Gray code for 5 (binary 101) is 7 (binary 111). Thus gray_decode(7) should return 5.

Your implementation must handle `n = 0` and values up to at least 2^31-1 (fits in a 32-bit signed integer). No bit-length argument is provided; the integer's own binary length is used.

Constraints

0 ≤ n ≤ 2^31 - 1. Time complexity O(log n) or better. Your solution should avoid using Python's built-in conversion functions that directly decode Gray code (none exist). You may use bitwise operations only.

Example

>>> gray_decode(0)
0
>>> gray_decode(1)
1
>>> gray_decode(2)
3
>>> gray_decode(7)
5
>>> gray_decode(15)
10

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about how the MSB is preserved and how XOR can bring back the original bits.

Masking after each shift prevents interference from higher bits.

Try a loop that shifts progressively by powers of two (1, 2, 4, ...) until the shift is larger than the integer's bit length.

The transformation is its own inverse: applying the same decoding twice returns the original, but you only need to do it once.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.