Binary to Gray code conversion algorithm is deceptively simple:

#### Gray code

Gray code is a binary code in which two consecutive values differ only by a single bit. Three-bit Gray code, along its binary counterpart, looks like this:

`N+1`-bit Gray code can be easily constructed from `N`-bit Gray code using the following process: This variant of Gray code is often called reflected binary Gray code. The “Vertical Flip” step is nothing else than creating a mirror image of the code in vertical direction.

The above process, with the fact that `1`-bit Gray code consists just of values `0` and `1`, allows us to write a recursive algorithm for converting between corresponding binary and Gray code values.

#### Recursive algorithm

We will define a function `G(nbits, n)` that returns `n`th `nbits`-bit Gray code value. `n` must be in range `0` .. `2**nbits - 1` (where `**` means power).

For `nbits` equal to 1 this is trivial:

we return `0` when `n` is zero, and one when `n` is one.

Next we need to translate the process from the first picture into code:

Where `msb` is a simple function that returns the most significant bit (MSB for short) of an `nbits`-bit number `n`:

Similarly we will use LSB term to refer to the least significant bit of a number.

There are two key observations that we must make to understand how the algorithm works. First observation is that binary values share the same value of MSB bit with the corresponding Gray code values. This is the result of the construction process, that adds leading zeros to the upper half (blue) of the Gray code, and leading ones to the lower half (red) of the code.

When `MSB = 0` we are in the upper half (blue) of the `nbits`-bit Gray code, which was constructed from the `nbits-1`-bit Gray code by adding extra `0` as a prefix to its values. In this case we just call recursively `G(nbits-1, n)` (`n` is in this case `< 2**nbits/2 = 2**(nbits-1)`), and add a `0` as a prefix to the result to finish the conversion to `nbits`-bit code.

When `MSB = 1` we are in the lower half (red) of the code, that was constructed by vertically flipping `nbits-1`-bit Gray code and adding `1` as a prefix to its values. The second key observation here, is the relationship between reflected `nbits-1`-bit Gray code and its non-reflected counterpart. `nbits-1`-bit Gray value that is located at `x`th position in the red (reflected) area is exactly the same as `2**(nbits-1)-1 - x`th value located in the blue area. To convert `n` into `nbits-1` Gray code, first we remove `1` MSB bit from it, converting it basically into our `x` (zero-based offset from the beginning of the red area; see the picture above). Then we compute position of `x`s counterpart in the non-reflected (blue) area of the code, by using expression:

Then we call `G(nbits-1, nonReflectedPos)` to compute `nbits-1`-bit Gray code value and finally we restore `1` bit prefix to it.

The above algorithm expressed in Java:

#### Using Strings to represent binary values

To further improve our algorithm we need to change our representation of binary values from 32-bit integers to strings. For example a string `"110"` will represent a `3`-bit binary value. We will also use empty string `""` to represent a sole zero-bit binary value (after all `2**0 = 1`, so there is one such value).

To proceed further, we need two simple facts. Fact 1: Numbers in form `2**k - 1` are represented in binary by sequence of `k` ones. For example `2**3-1 = 7` is `111` in binary.

Fact 2: Substracting `k`-bit value `p` from `1...1` (`k` ones) is equal to negating `p`:

These both facts will allow us to rewrite the expression for computing `nonReflectedPos` value from:

to

Our previous algorithm changed to use strings and expressed in JavaScript:

#### The single-line algorithm

If we now look at the code of our algorithm, we may see that all it does is to negate the unseen part of the input every time we encounter `1` bit: Let us consider how our algorithm will transform groups of ones followed by a single zero bit (`11...110`): As we can see group of `11...110` bits is transformed into `10...01`, but what is more important: bits that are after this group remain unchanged. Similarly groups of ones without trailing zero (`1...1`), which may only occur at the end of the input are transformed into `10...0`.

Now is the time for another key observation: the above transformations can be performed by XORing value with itself shifted right by one: This works because after the shift every group of ones must be preceded by at least a single zero bit. Additionally every group of ones (except when the ones occur at the end of the input) must be followed by at least one zero bit. In other words different groups of ones are not interfering with each other while XORing.

Also notice that we must use right-shift operation that always shifts-in a zero bit. In Java this means using `>>>` (unsigned right shift) instead of `>>` operator.

Source code (GitHub Gist): grayBin.js