Binary to Gray code conversion algorithm is deceptively simple:

in this article I will explain how it works.

#### 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