## Gray Code Neighbors

### December 2, 2014

Two numbers *a* and *b* are neighbors in a Gray code sequence if they differ by a single bit. Thus, we can take the xor of two numbers and check if the result is a power of two:

`(define (neighbors? a b)`

(let ((x (logxor a b)))

(= (logand x (- x)) x)))

The trick is in the last line. If *x* is a power of two, with its lone 1-bit is in the *n* th position of the number, then *x* − 1 must have a 0-bit in the *n* th position. To make the subtraction, the borrow propagates all the way to the *n* th position, the *n* th bit becomes 0 and all lower bits are 1. For both *x* and *x* − 1, all higher bits are 0, so the logical and of *x* and −*x* will be *x*.

For instance:

`> (neighbors 88 72)`

#t

> (neighbors 88 89)

#t

> (neighbors 88 90)

#t

> (neighbors 88 91)

#f

We used `logxor`

and `logand`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/8gyN1oVP.

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.

The 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:

“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.