Hacker's Delight

13-1. Gray Code

Is it possible to cycle through all 2ⁿ combinations of n bits by changing only one bit at a time? The answer is “yes,” and this is the defining property of Gray codes. That is, a Gray code is an encoding of the integers such that a Gray-coded integer and its successor differ in only one bit position. This concept can be generalized to apply to any base, such as decimal, but here we will discuss only binary Gray codes.

Although there are many binary Gray codes, we will discuss only one: the “reflected binary Gray code.” This code is what is usually meant in the literature by the unqualified term “Gray code.” We will show, usually without proof, how to do some basic operations in this representation of integers, and we will show ...