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

Question

我正在尝试解决一个问题，即给定两个数字，找出它们是否是格雷码序列中的连续数字，即它们是否是格雷码邻居，假设未提及格雷码序列。

我在各种论坛上搜索，但没有得到正确的答案。如果您能提供解决方案，那将非常好。

我的解决方法是 - 将两个整数转换为二进制，并分别添加两个数字中的数字，然后找到两个数字中数字总和之间的差异。如果差为一，则它们是格雷码邻居。

但我觉得这种方法并不适用于所有情况。非常感谢您的帮助。提前致谢！

- user3923643

---

如果a XOR b是2的幂，则a和b是格雷码相邻数，即它们唯一不同的是一位。 - Peter de Rivaz

请注意，这里有许多格雷码序列。您是否有特定的序列想法，或者您想知道两个数字是否可以在_某些_格雷码序列中成为相邻的？ - ErikR

非常感谢您的回复。请问是否有可能知道给定的两个数字在某个序列中是否是格雷码相邻数？问题中没有指定序列。我在一次面试中遇到了这个问题。非常感谢任何帮助！ - user3923643

Answer 1

实际上，其他一些答案似乎是错误的：两个二进制反射格雷码邻居仅相差一位（我假设您所说的“the”格雷码序列指的是由弗兰克·格雷描述的原始二进制反射格雷码序列）。但是，这并不意味着相差一位的两个格雷码是邻居（a => b并不意味着b => a）。例如，格雷码1000和1010仅相差一位，但它们不是邻居（在十进制中，分别为15和12）。

如果您想知道两个格雷码a和b是否是邻居，您必须检查previous(a)=b或next(a)=b。对于给定的格雷码，通过翻转最右边的位可以得到一个邻居，通过翻转右侧最右侧集合位的左侧位可以得到另一个邻居。对于格雷码1010，邻居是1011和1110（1000不是它们之一）。

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

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

上面的位操作技巧: a & -a 可以隔离一个数字中最右边的那个置位位。我们将该位向左移动一位即可得到需要翻转的位。

- Morwenn

---

很棒的解决方案。这是所有方案中最好的，也是正确的。干得好，伙计。 - Sameer Sawla

根据 https://math.stackexchange.com/questions/965168/find-the-neighbors-in-gray-code-sequence 上的被接受的答案，你的伪代码无法遍历所有邻居可能性。同样长度的两个格雷码序列的例子：[000,001,011,010,110,111,101,100]，[000,001,011,111,101,100,110,010]。代码 000 可能有超过两个合法的邻居。 - Di Wu

@DiWu 当然，我的回答假设是一个二进制反射格雷码序列，这通常是人们在没有指定时所询问的序列。 - Morwenn

Answer 2

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

#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

一些测试用例：

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

参考文献: 上方使用的gTob()方法来自rodrigo在这篇文章中The neighbors in Gray code

- codeKaichu

Answer 3

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

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

}

- Varun Dixit

---

请在回答中加入一些解释，说明您为什么认为这个回答解决了提问者的问题。 - iRuth

你尝试阅读并理解被接受的答案和Morwenn的回答，以及它们为什么被评级不同了吗？ - greybeard

Answer 4

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

这种解决方案对CodeKaichu上面提到的所有测试用例都有效。我很想知道它是否在任何情况下失败。

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

- Ravikanth

Answer 5

一个显而易见的答案，但它是有效的。 将每个格雷码转换为其相应的二进制形式，然后相减。如果你的答案是+1或-1的二进制等价物，则这两个格雷码是相邻的。

这似乎有些过度，但当你坐在面试中不知道正确的方法时，这很有效。此外，为了优化，我们可以检查单比特差异过滤器，这样我们就不会浪费时间转换和相减那些我们确定不相邻的数字。

- leo

Answer 6

如果你只想检查输入的数字是否仅相差一个比特：

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

- codeKaichu

Answer 7

您可以按照以下方式检查两个数字是否相差一个比特。在此方法中，二进制数的长度差异得到了处理。例如，11（1011）和3（11）的输出将返回为true。 此外，这并不能解决格雷码邻接的第二个标准。但是，如果您只想检查数字是否相差一个比特，则下面的代码将有所帮助。

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

- Aswin

---

踩票是为了什么？我已经清楚地提到这种方法只检查第一个标准。在技术公司的面试中，他们要求我编写特定任务的代码，而不是对确切的格雷码邻接测试感兴趣。 - Aswin

Answer 8

如果两个数字在格雷码序列中，它们的二进制数位差值为1。即这两个数字的异或结果是2的幂次方。因此，找到异或值并检查结果是否为2的幂次方。

Python 3.8

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

- kabali

---

这似乎与David.Jones错误的被接受的答案没有区别。 - greybeard

Answer 9

我也曾在面试中遇到过这个问题。判断两个值是否是格雷码序列的条件之一是它们的值只相差一位。以下是解决此问题的方案：

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

- David.Jones

---

这个答案是错误的。请参考Morwenn的回答。 - Craig McQueen

确实，相邻的格雷码只有一位不同。但这并不意味着只有一位不同的两个格雷码就一定是相邻的（a => b 不代表 b => a）。 - Morwenn