# Explicit formula for Nth string of Gray Code.

From Wolfram MathWorld, we have:

"A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a "reflected" code, or more specifically still, the binary reflected Gray code (...). The code is called reflected because it can be generated in the following manner. Take the Gray code 0, 1. Write it forwards, then backwards: 0, 1, 1, 0. Then prepend 0s to the first half and 1s to the second half: 00, 01, 11, 10. Continuing, write 00, 01, 11, 10, 10, 11, 01, 00 to obtain: 000, 001, 011, 010, 110, 111, 101, 100, ..."

Therefore, to obtain the n-th string, must know all the previous strings. Is there a mathematical formula that can return the nth string without knowing the first n-1 strings?

Thank you very much.

• The Wikipedia article on Gray code describes the algorithm you want. – MJD Oct 31 '14 at 12:26
• Here's a direct link to the (non-recursive) algorithm on Wikipedia. – Snowball Oct 31 '14 at 14:21
• But these algorithms require the knowledge of previous strings – Mark Oct 31 '14 at 23:40
• @Mark: The algorithm binaryToGray from the section of the Wikipedia article I linked to gives the $n^{\text{th}}$ entry in the binary reflected Gray code with no reference to previous entries. The only parameter is $n$ (well, num), and it operates in constant time. – Snowball Nov 6 '14 at 0:57
• Here's the formula in mathematical notation rather than C: Suppose you want to find the $n^{\text{th}}$ entry in the binary reflected Gray code. Write $n = (b_k b_{k-1} \cdots b_1)_2$ where $b_i$ are the digits of $n$ in binary. Then the corresponding Gray code entry is $(0, b_k, \ldots, b_3, b_2) + (b_k, b_{k-1}, \ldots, b_2, b_1)$, where addition is done elementwise modulo 2. – Snowball Nov 6 '14 at 1:04

## 1 Answer

The same MathWorld article you link has

To convert a binary number $d_1d_2\ldots d_{n-1}d_n$ to its corresponding binary reflected Gray code, start at the right with the digit $d_n$ (the $n$th, or last, digit). If the $d_{n-1}$ is $1$, replace $d_n$ by $1-d_n$; otherwise, leave it unchanged. Then proceed to $d_{n-1}$. Continue up to the first digit $d_1$, which is kept the same since $d_0$ is assumed to be a $0$. The resulting number $g_1g_2\ldots g_{n-1}g_n$ is the reflected binary Gray code.