Binary to Gray code conversion algorithm is deceptively simple:
in this article I will explain how it works.
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
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
allows us to write a recursive algorithm for converting
between corresponding binary and Gray code values.
We will define a function
G(nbits, n) that returns
nbits-bit Gray code value.
n must be in range
2**nbits - 1
** means power).
nbits equal to 1 this is trivial:
n is zero, and one when
n is one.
Next we need to translate the process from the first picture into code:
msb is a simple function that returns
the most significant bit (MSB for short) of
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.
MSB = 0 we are in the upper half (blue) of the
Gray code, which was constructed from the
code by adding extra
0 as a prefix to its values.
In this case we just call recursively
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
MSB = 1 we are in the lower half (red) of the code, that
was constructed by vertically flipping
code and adding
1 as a prefix to its values.
The second key observation here, is the relationship between
nbits-1-bit Gray code and its non-reflected counterpart.
nbits-1-bit Gray value that is located
xth position in the red (reflected)
area is exactly the same as
2**(nbits-1)-1 - xth value located in the blue area.
nbits-1 Gray code, first
1 MSB bit from it, converting
it basically into our
(zero-based offset from the beginning of the red area; see the picture above).
Then we compute position of
xs counterpart in
the non-reflected (blue) area of the code, by using expression:
Then we call
G(nbits-1, nonReflectedPos) to
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
3-bit binary value. We will also use empty string
"" to represent a sole zero-bit binary value
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
2**3-1 = 7 is
111 in binary.
Fact 2: Substracting
is equal to negating
These both facts will allow us to rewrite
the expression for computing
nonReflectedPos value from:
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
Let us consider how our algorithm will transform
groups of ones followed by a single zero bit (
As we can see group of
11...110 bits is transformed into
but what is more important: bits that are after this group remain unchanged.
Similarly groups of ones without trailing zero (
which may only occur at the end of the input are transformed into
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)
Source code (GitHub Gist): grayBin.js