How to find if two numbers are consecutive numbers

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!!!

Answer 1

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

Answer 2

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;
}