Gray Code Neighbors
December 2, 2014
Our exercise today is based on Gray code sequences, where each number in the sequence differs from its predecessor in only one bit. We studied Gray code sequences in a previous exercise. Here is an interview question base on Gray code sequences:
Given two integers, determine if they are two consecutive numbers in a Gray code sequence.
Your task is to write a program that determines if two numbers appear consecutively in a Gray code sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Hello everybody, i have some questions:
1. Is it enough to check if the two numbers differ in only one bit? Is it not possible that they differ only in one bit but they are not consecutive members of any Gray sequence?
For example take a 3 bit Gc sequence: 000 – 100 – 110 – 111 – 011 – 010 – … It cannot be completed because all the next three possible values (110, 000, 011) are in the sequence yet.
Maybe my undestandig of Gray codes are wrong.
2. Do a Gray code sequence starts always with 0 value?
3. Do we consider only Gc sequences that are complete?
4. I do not know the math behind Gray codes, but can we say, that the first and the last elements of a complete Gc sequence differ in one bit too?
Thanks for the answers!
Andras
@Andras : If two numbers differ in more than one bit, then they cannot be adjacent numbers in a Gray code sequence.
However, two numbers that differ by only one bit, may not be adjacent in a Gray code sequence. For example, consider the 3-bit binary reflected gray code: 000 – 001 – 011 – 010 – 110 – 111 – 101 – 100 – 000. The numbers 000 and 010 differ by only a single bit, but they are not adjacent in the sequence. In general, for an n-bit Gray code, each code differs from n other codes by a single bit, yet only two of the other codes are adjacent to it in a specific Gray code sequence.
The problem mentioned a previous exercise on binary reflected grey code (BRGC). So, here is a solution assuming the Gray codes sequence is a BRGC.
# # convert a binary-reflected gray code to its index in the sequence # def BRGC_to_binary(code): mask = code >> 1 while mask: code ^= mask mask >>= 1 return code # # check if the indices are adjacent modulo the length of the gray code sequence # def are_adjacent(n, m, nbits=8): numcodes = 1 << nbits ni = BRGC_to_binary(n) mi = BRGC_to_binary(m) return (ni + 1)% numcodes == mi or (mi + 1)%numcodes == niThe above code iterates over the bits in each number so is O(bitlen(m)+bitlen(n)), where bitlen() is the number of significant bits.
Here is a non-iterative solution that uses bit wise operations:
def are_adjacent(n, m, nbits=8): diff = n ^ m if diff and ((diff & -diff) ^ diff) == 0: if (n & (diff - 1)) == (diff >> 1) or n & m == 0 and n | m == 1 << nbits - 1: return True return False“diff” is a bit map of the bits that are different between n and m.
“if diff” makes sure there is at least one changed bit.
“… and ((diff & -diff) ^ diff) == 0” makes sure there is only one changed bit.
“if (n & (diff – 1)) == (diff >> 1)” makes sure bits to the right of the changed bit are of the form (10*)?.
“…or n & m == 0 and n | m == 1 << nbits – 1" makes sure one of n and m is zero and the other equals the msb.
@Andras and Mike: if two numbers differ by only one bit, one can always find a Gray sequence in which they take consecutive places. To do so, first observe that, given any Gray sequence, if you swap two columns of it you get another Gray sequence. To construct a sequence for two given numbers that differ by one bit, you could count the number of bits in the numbers, find an occurrence of neighbours with the same number of bits in the BRGC and swap columns to match your desired numbers.