How to find if two numbers are consecutive numbers in gray code sequence

Question

I am trying to come up with a solution to the problem that given two numbers, find if they are the consecutive numbers in the gray code sequence i.e., if they are gray code neighbors assuming that the gray code sequence is not mentioned.

I searched on various forums but couldn't get the right answer. It would be great if you can provide a solution for this.

My attempt to the problem - Convert two integers to binary and add the digits in both the numbers separately and find the difference between the sum of the digits in two numbers. If the difference is one then they are gray code neighbors.

But I feel this wont work for all cases. Any help is highly appreciated. Thanks a lot in advance!!!

Magpie

a and b are gray code neighbours if they only differ in one bit, i.e. if a XOR b is a power of 2. – Usurious

Note that here are many Gray code sequences. Do you have a specific sequence in mind, or do you want to know if two numbers could be neighbors in some Gray code sequence? – Masterpiece

Thanks a lot for your responses. Is it possible to know if the given two numbers are gray code neighbors in some sequence? The sequence was not specified in the question. I came across in one of the interviews. Any help is appreciated!!! – Magpie

Answer 1

I've had to solve this question in an interview as well. One of the conditions for the two values to be a gray code sequence is that their values only differ by 1 bit. Here is a solution to this problem:

def isGrayCode(num1, num2):
    differences = 0
    while (num1 > 0 or num2 > 0):
        if ((num1 & 1) != (num2 & 1)):
            differences++
        num1 >>= 1
        num2 >>= 1
    return differences == 1

Jamesjamesian

This answer is wrong. See Morwenn's answer. – Perkins

@DavidJones « [...] it's true that two Gray code neighbours differ by only one bit. However, that does not mean that two Gray codes differing by one bit are neighbours (a => b does not mean that b => a). » – Trimester

Answer 2

Actually, several of the other answers seem wrong: it's true that two binary reflected Gray code neighbours differ by only one bit (I assume that by « the » Gray code sequence, you mean the original binary reflected Gray code sequence as described by Frank Gray). However, that does not mean that two Gray codes differing by one bit are neighbours (a => b does not mean that b => a). For example, the Gray codes 1000 and 1010 differ by only one bit but are not neighbours (1000 and 1010 are respectively 15 and 12 in decimal).

If you want to know whether two Gray codes a and b are neighbours, you have to check whether previous(a) = b OR next(a) = b. For a given Gray code, you get one neighbour by flipping the rightmost bit and the other neighbour bit by flipping the bit at the left of the rightmost set bit. For the Gray code 1010, the neighbours are 1011 and 1110 (1000 is not one of them).

Whether you get the previous or the next neighbour by flipping one of these bits actually depends on the parity of the Gray code. However, since we want both neighbours, we don't have to check for parity. The following pseudo-code should tell you whether two Gray codes are neighbours (using C-like bitwise operations):

function are_gray_neighbours(a: gray, b: gray) -> boolean
    return b = a ^ 1 OR
           b = a ^ ((a & -a) << 1)
end

Bit trick above: a & -a isolates the rigthmost set bit in a number. We shift that bit by one position to the left to get the bit we need to flip.

Trimester

Awesome solution. This is best one out of all and the correct one too. Nice job man. – Bunyip

Based on the accepted answer at math.stackexchange.com/questions/965168/… , your pseudo-code is not able to go through all the neighbour possibilities. Example of two Gray Code sequences of the same length: [000,001,011,010,110,111,101,100], [000,001,011,111,101,100,110,010]. The code 000 could have more than two legit neighbours. – Dianetics

@DiWu Of course, my answer assumes a binary reflected Gray code sequence, which is generally the one people are saking about when nothing is specified. – Trimester

Answer 3

Assumptions: Inputs a and b are grey code sequences in binary reflected gray code. i.e a's and b's bit encoding is binary gray code representations.

#convert from greycode bits into regular binary bits
def gTob(num): #num is binary graycode 
    mask = num >> 1
    while mask!=0:
        num = num^mask
        mask >>= 1
    return num; #num is converted 

#check if a and b are consecutive gray code encodings
def areGrayNeighbors(a,b):
    return abs(gTob(a) - gTob(b)) == 1

Few Test cases:

• areGrayNeighbors(9,11) --> True (since (1001, 1011) differ in only one bit and are consecutive numbers in decimal representation)
• areGrayNeighbors(9,10) --> False
• areGrayNeighbors(14,10) --> True

References: method gTob() used above is from rodrigo in this post The neighbors in Gray code

Latrishalatry

Answer 4

public int checkConsecutive2(int b1, int b2){
    int x =  (b1 ^ b2);

    if((x & (x - 1)) !=0){
      return 0;
    }else{
      return 1;
    }

}

Covenant

Please add a little explanation as to why you think this answers the OP's question. – Mobilize

Did you try to read and understand the accepted answer and Morwenn's, and why they are rated differently? – Housewares

Answer 5

If two numbers are in gray code sequence, they differ by one binary digit. i.e the exclusive OR on the two numbers returns a power of 2. So, find XOR and check if the result is a power of two.

This solution works well for the all the test cases written by CodeKaichu above. I would love to know if it fails in any cases.

public boolean grayCheck(int x, int y) {
       int z = x^y;
       return (z&z-1)==0;
}

Minyan

Answer 6

An obvious answer, but it works. Convert each gray code into its respective Binary form, subtract the two. If you answer is a binary equivalent of +1 or -1 then the two gray codes are adjacent.

This seems like an over kill, but when you're siting in an interview and don't know the correct method, this works. Also to optimize, one can check the single bit difference filter, so we don't waste time converting and subtracting numbers that we know for sure aren't adjacent.

Hutcheson

Answer 7

If you just want to check if the input numbers differ by just one bit:

public boolean checkIfDifferByOneBit(int a, int b){
    int diff = 0;
    while(a > 0 && b > 0){
        if(a & 1 != b & 1)
            diff++;
        a = a >> 1;
        b = b >> 1;
    }
    if (a > 0 || b > 0) // a correction in the solution provided by David Jones
        return diff == 0 // In the case when a or b become zero before the other
    return diff == 1;
}

Latrishalatry

Answer 8

You can check if two numbers differ by one bit or not as follows. In this method, difference in the length of binary numbers are taken care of. Eg, the output for 11 (1011) and 3 (11) will be returned as true. Also, this does not solve the second criteria for Gray code adjacency. But if you only want to check if the numbers differ by one bit, the code below will help.

class Graycode{
    public static boolean graycheck(int one, int two){
        int differences = 0;
        while (one > 0 || two > 0){
            // Checking if the rightmost bit is same
            if ((one & 1) != (two & 1)){
                differences++;
            }
            one >>= 1;
            two >>= 1;
        }
        return differences == 1;
    }
    public static void main(String[] args){
        int one = Integer.parseInt(args[0]);
        int two = Integer.parseInt(args[1]);
        System.out.println(graycheck(one,two));
    }
}

Joline

What's the down vote for? I've clearly mentioned that this method only checks the first criteria. During interviews at tech companies, I've been asked to write the code for this specific task and they were not interested in the exact Gray Code adjacency test. – Joline

Answer 9

If two numbers are in gray code sequence, they differ by one binary digit. i.e the exclusive OR on the two numbers returns a power of 2. So, find XOR and check if the result is a power of two.

python 3.8

a=int(input())
b=int(input())
x=a^b 
if((x and (not(x & (x - 1))) )):
    print("True")
else:
    print("False")

Blaylock

This does not seem to differ from David.Jones's erroneous accepted answer. – Housewares