javapythoncalgorithmgray-code

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


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


Solution

  • 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