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

Question

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

I searched in various forums, but could not get the correct answer. It would be great if you could provide a solution for this.

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

But I feel that this will not work for all cases. Any help is much appreciated. Thanks a lot in advance!

Answer 1

I had to solve this issue in an interview. One of the conditions for the two values ​​is the sequence of gray code, consisting in the fact that their values ​​differ by only 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 

Answer 2

In fact, some of the other answers seem to be wrong: it is true that the two binary reflected binary code of the Gray code differs by only one bit (I assume that by using the "gray" sequence of Gray code you mean the original binary reflected code sequence of Gray, as described by Frank Gray). However, this does not mean that two Gray codes that differ by one bit are neighbors ( a => b does not mean that b => a ). For example, the codes Gray 1000 and 1010 differ by only one bit, but are not neighbors (1000 and 1010 are respectively 15 and 12 in decimal form).

If you want to know if the two gray codes a and b neighbors, you should check if previous(a) = b OR next(a) = b . For a given Gray code, you get one neighbor by flipping the rightmost bit and another neighbor bit by flipping the bit to the left of the rightmost set bit. For gray code 1010, neighbors are 1011 and 1110 (1000 is not one of them).

Whether you get the previous or next neighbor by flipping one of these bits actually depends on the parity of the Gray code. However, since we want both neighbors, we do not need to parity. The following pseudo code should tell you if two Gray codes are neighbors (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 a fixed-set bit quantity. We shift this bit one position to the left to get the bit that we need to flip.

Answer 3

Assumptions: Inputs a and b are gray code sequences in binary reflected gray code. ie a and b-bit encoding are 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 

Several test cases:

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

References: The gTob () method used above from rodrigo in this post. Neighbors in Gray Code

Answer 4

 public int checkConsecutive2(int b1, int b2){ int x = (b1 ^ b2); if((x & (x - 1)) !=0){ return 0; }else{ return 1; } } 

Answer 5

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

This solution is well suited for all test cases written by CodeKaichu above. I would like to know if this fails anyway.

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

Answer 6

The obvious answer, but it works. Convert each gray code to the corresponding binary form, subtract two. If you answer the binary equivalent of +1 or -1, then the two gray codes are adjacent.

It is like killing, but when you sit in an interview and don’t know the right method, it works. Also, for optimization, you can check the filter with a difference bit difference, so we do not waste time converting and subtracting numbers that, as we know, are not adjacent.

Answer 7

If you just want to check if the input numbers differ by 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; } 

Answer 8

You can check if two numbers differ by one bit or not as follows. This method takes care of the difference in the length of the binary numbers. For example, the output for 11 (1011) and 3 (11) will be returned as true. In addition, this does not solve the second gray code adjacency criterion. But if you only want to check if the digits 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)); } }