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.

Pages: 1 2

3 Responses to “Gray Code Neighbors”

  1. Andras said

    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

    @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

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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: