6

我试图想出一个解决方案，给定两个数字，找出它们是否是格雷码序列中的连续数字，即，如果它们是格雷码邻居，假设没有提到格雷码序列。

我在各种论坛上搜索，但无法得到正确的答案。如果您可以为此提供解决方案，那就太好了。

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

但我觉得这不适用于所有情况。非常感谢任何帮助。非常感谢提前！！！

4

9 回答 9

32

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

如果你想知道两个格雷码a和b是否是邻居，你必须检查是否previous(a) = b OR 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隔离数字中最正确的设置位。我们将该位向左移动一个位置以获得我们需要翻转的位。

于 2014-12-06T14:32:00.170 回答
1

假设：输入 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

几个测试用例：

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

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

于 2014-12-27T23:30:42.730 回答
0 
public int checkConsecutive2(int b1, int b2){
    int x =  (b1 ^ b2);

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

}
于 2015-03-25T21:32:32.620 回答
0

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

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

public boolean grayCheck(int x, int y) {
       int z = x^y;
       return (z&z-1)==0;
}
于 2015-04-16T03:28:58.513 回答
0

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

这似乎是一种过度杀戮，但是当你在面试中并且不知道正确的方法时，这很有效。另外为了优化，可以检查单个位差过滤器，因此我们不会浪费时间转换和减去我们确定不相邻的数字。

于 2015-09-07T16:59:06.910 回答
-1

您可以检查两个数字是否相差一位，如下所示。在这种方法中，处理了二进制数长度的差异。例如，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));
    }
}
于 2015-03-02T03:01:00.397 回答
-1

如果您只想检查输入数字是否仅相差一位：

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;
}
于 2014-12-27T22:34:29.800 回答
-1

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

蟒蛇3.8

a=int(input())
b=int(input())
x=a^b 
if((x and (not(x & (x - 1))) )):
    print("True")
else:
    print("False")
于 2020-11-21T09:40:21.380 回答
-7

我也不得不在面试中解决这个问题。这两个值成为格雷码序列的条件之一是它们的值仅相差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
于 2014-11-30T22:38:09.513 回答