如何查找两个数字是否为格雷码序列中的连续数字
我试图找到给出两个数字的问题的解决方案，找出它们是否是格雷码序列中的连续数字，即，如果它们是灰色代码邻居，假设没有提到格雷码序列。
我在各种论坛上搜索但无法得到正确的答案。 如果您能为此提供解决方案，那就太棒了。
我试图解决这个问题 – 将两个整数转换为二进制并分别在两个数字中加上数字，并找出两个数字中数字之和的差值。 如果差异为1，则它们是格雷码邻居。
但我觉得这不适用于所有情况。 任何帮助都非常感谢。 非常感谢提前！
我也必须在面试中解决这个问题。 两个值为格雷码序列的条件之一是它们的值仅相差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 实际上，其他几个答案似乎都是错误的：两个二进制reflection格雷码邻居确实只有一位（我假设通过«格雷码序列，你的意思是原始二进制reflection格雷码序列，如格雷格格雷所描述的那样） ）。 然而，这并不意味着相差一位的两个格雷码是邻居（ 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隔离数字中最严格的设置位。 我们将该位向左移动一个位置以获得我们需要翻转的位。
假设：输入a和b是二进制reflection格雷码中的格雷码序列。 即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） – >错
- areGrayNeighbors（14,10） – >真的
参考文献：上面使用的方法gTob（）来自本文中的rodrigo 格雷码中的邻居
public int checkConsecutive2(int b1, int b2){ int x = (b1 ^ b2); if((x & (x - 1)) !=0){ return 0; }else{ return 1; } }
如果两个数字是格雷码序列，则它们相差一个二进制数字。 即两个数字上的异或返回2的幂。因此，找到XOR并检查结果是否为2的幂。
此解决方案适用于上面CodeKaichu编写的所有测试用例。 我想知道它是否在任何情况下都失败了。
public boolean grayCheck(int x, int y) { int z = x^y; return (z&z-1)==0; }
一个明显的答案，但它的工作原理。 将每个格雷码转换为各自的二进制格式，减去这两个格式。 如果你回答的是等价于+1或-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; }
您可以检查两个数字是否相差一位，如下所示。 在该方法中，考虑二进制数长度的差异。 例如，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)); } }