Hacker's Delight

13-3. Negabinary Gray Code

If you write the integers in order in base −2, and convert them using the “shift and exclusive or” that converts to Gray from straight binary, you get a Gray code. The 3-bit Gray code has indexes that range over the 3-bit base −2 numbers, namely −2 to 5. Similarly, the 4-bit Gray code corresponding to 4-bit base −2 numbers has indexes ranging from −10 to 5. It is not a reflected Gray code, but it almost is. The 4-bit Gray code can be generated by starting with 0 and 1, reflecting this about a horizontal axis at the top of the list, and then reflecting it about a horizontal axis at the bottom of the list, and so on. It is cyclic.

To convert back to base −2 from this Gray code, the rules are of course the same as they ...