Is there any practical trick to mentally count in Gray code?

Question

When I was fairly young, I taught myself to count in binary. I thought it would be a fun party trick to impress people. I soon found out that it was not.

Over the years I've come to appreciate Gray code/reflected binary code for its property of only flipping one bit for each increment/decrement of the underlying count. But I've always been bothered by the fact that, if I wanted to mentally take any arbitrary Gray code and add or subtract 1 from it, I'd have to either convert it to and then back from its numeric value, or construct a table to work out what the next code should be.

It seems to me that there should be some trick that a person with "average" short term memory and addition skills should be able to do to take any arbitrary value in Gray code and figure out which bit to flip to get the next value... But I've never found it.

Does such a thing exist?

Answer 1

I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer will carry through larger values too.

Take a Gray code, and count the number of 1's:

Case I:
Odd number of 1's: flip the bit one position before the last '1'.
Case II:
Even number of 1's: flip the last bit.

Examples:

Even case: After 10100101, the next one is 10100100.

Explanation: there are 4 1's so we apply the even case, i.e., flip the last bit.

After 111011010, the next one is 111011011.

Explanation: there are 6 1's so we again flip the last bit.

Odd case: After 110111, the next one is 110101.

Explanation: there are 5 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.

After 1100100, the next one is 1101100.

Explanation: there are 3 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.

I hope this helps!

Answer 2

The title of my masters thesis was Efficient Hardware Implementations of Gray Code Arithmetic. The goal was to find a way to, at the digital hardware level, perform arithmetic on Gray code directly without first converting to binary. Spoiler alert: I never did find a way to do that. What I did find was a way to convert from Gray code to binary more quickly (in logarithmic rather than linear time). If I'm remembering correctly, converting from binary back to Gray code is already fast.

Now I did come up with a fast Gray code numeric comparitor, i.e. a circuit that could compare the value of two numbers expressed in Gray code, that did not require initial conversion to binary.

Answer 3

Gray codes are hamilton cycles in hypercube graphs $Q_n$, which can be recursively constructed using Hamilton cycles in $Q_{n-1}$. Perhaps you can do these computations by hand for small n and see if that helps.

Answer 4

Wikipedia describes a very simple algorithm for this task:

To construct the binary-reflected Gray code iteratively, at step 0 start with the $\text{code}_0 = 0$, and at step $i > 0 $ find the bit position of the least significant 1 in the binary representation of $i$ and flip the bit at that position in the previous code $\text{code}_{i-1}$ to get the next code $\text{code}_i$.

Source: https://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_Gray_code

This is certainly simple enough to do in your head.

This works if you are willing to start at 0 and increment one at a time (since then you can remember how many times you've incremented), but if someone else is going to give you an arbitrary bitstring and ask you to find the next Gray code, this isn't of any use (it would require converting the Gray code back to an ordinary integer, which might be harder).