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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Gray Code Neighbors”

  1. Andras said
    December 2, 2014 at 1:19 PM

    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

  2. Mike said
    December 3, 2014 at 12:40 AM

    @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 == ni

    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:

    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.

  3. Daniel said
    December 4, 2014 at 1:23 PM

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

Leave a comment