java 如何在格雷码序列中查找两个数字是否是连续数字

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

提问by user3923643

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.

我对这个问题的尝试 - 将两个整数转换为二进制并分别将两个数字中的数字相加，然后找出两个数字中数字总和的差值。如果差为 1，则它们是格雷码邻居。

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

但我觉得这不适用于所有情况。任何帮助都受到高度赞赏。非常感谢提前！！！

采纳答案by David.Jones

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:

我也不得不在采访中解决这个问题。两个值成为格雷码序列的条件之一是它们的值仅相差1位。下面是这个问题的解决方案：

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

回答by Morwenn

Actually, several of the other answers seem wrong: it's true that two binary reflected Gray codeneighbours 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 => bdoes 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).

实际上，其他几个答案似乎是错误的：两个二进制反射格雷码邻居确实只有一位不同（我假设通过 ??the?? 格雷码序列，您的意思是原始二进制反射格雷码序列，如弗兰克·格雷）。然而，这并不意味着相差一位的两个格雷码是相邻的（a => b并不意味着b => a）。例如，格雷码 1000 和 1010 仅相差一位，但不是邻居（1000 和 1010 分别是十进制的 15 和 12）。

If you want to know whether two Gray codes aand bare 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).

如果你想知道两个格雷码a和是否b是邻居，你必须检查previous(a) = b OR next(a) = b。对于给定的格雷码，您可以通过翻转最右边的位来获得一个邻居，而通过翻转最右边的设置位左侧的位来获得另一个邻居位。对于格雷码 1010，邻居是 1011 和 1110（1000 不是其中之一）。

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):

通过翻转这些位中的一个来获得前一个或下一个邻居实际上取决于格雷码的奇偶校验。但是，因为我们想要两个邻居，所以我们不必检查奇偶性。以下伪代码应该告诉您两个格雷码是否相邻（使用类似 C 的按位运算）：

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

Bit trick above: a & -aisolates 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.

上面的位技巧：a & -a隔离数字中最严格的设置位。我们将该位向左移动一个位置以获得我们需要翻转的位。

回答by codeKaichu

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.

假设：输入 a 和 b 是二进制反射格雷码中的格雷码序列。即a's 和b's 位编码是二进制格雷码表示。

#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

• areGrayNeighbors(9,11) --> True （因为 (1001, 1011) 只有一位不同，并且是十进制表示中的连续数字）
• areGrayNeighbors(9,10) --> False
• areGrayNeighbors(14,10) --> 真

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

参考：上面使用的方法 gTob() 来自这篇文章中的罗德里戈格雷码中的邻居

回答by Varun Dixit

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

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

}

回答by Ravikanth

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.

如果两个数字在格雷码序列中，它们相差一位二进制数。即两个数字的异或返回 2 的幂。因此，找到 XOR 并检查结果是否为 2 的幂。

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.

该解决方案适用于上述 CodeKaichu 编写的所有测试用例。我很想知道它是否在任何情况下都会失败。

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

回答by leo

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.

一个明显的答案，但它有效。将每个格雷码转换为其各自的二进制形式，将两者相减。如果你的答案是 +1 或 -1 的二进制等价物，那么这两个格雷码是相邻的。

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.

这似乎有点过头了，但是当你在面试时不知道正确的方法时，这很有效。同样为了优化，可以检查单个位差分过滤器，因此我们不会浪费时间转换和减去我们确定不相邻的数字。

回答by Aswin

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.

您可以检查两个数字是否相差一位，如下所示。在这种方法中，处理了二进制数长度的差异。例如，11 (1011) 和 3 (11) 的输出将返回为真。此外，这并没有解决格雷码邻接的第二个标准。但是如果你只想检查数字是否相差一位，下面的代码会有所帮助。

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

回答by codeKaichu

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