patternMinor
Is there any practical trick to mentally count in Gray code?
Viewed 0 times
mentallytrickgrayanypracticalcodecountthere
Problem
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?
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?
Solution
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!
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!
Context
StackExchange Computer Science Q#62887, answer score: 5
Revisions (0)
No revisions yet.