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

Question

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

我在各种论坛上进行了搜索，但找不到正确的答案。如果您能为此提供解决方案，那就太好了。

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

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

Answer 1

实际上，其他几个答案似乎是错误的:两个二进制反射格雷码邻居确实只相差一位(我假设“格雷码序列”是指原始的Frank Gray 描述的二进制反射格雷码序列)。然而，这并不意味着相差一位的两个格雷码是邻居(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 隔离数字中最右边的设置位。我们将该位向左移动一个位置以获得我们需要翻转的位。