格雷码中的邻居

我可以使用任何算法在格雷码中找到邻居吗？

对于小数字来说，编写整个表格就好了，但是如果我有一个像010这样的数字，那么用6个数字编写整个灰色代码表有点太多了。

Answer 1

从维基百科无耻地复制：

/* The purpose of this function is to convert an unsigned binary number to reflected binary Gray code. The operator >> is shift right. The operator ^ is exclusive or. */ unsigned int binaryToGray(unsigned int num) { return (num >> 1) ^ num; } /* The purpose of this function is to convert a reflected binary Gray code number to a binary number. */ unsigned int grayToBinary(unsigned int num) { unsigned int mask; for (mask = num >> 1; mask != 0; mask = mask >> 1) { num = num ^ mask; } return num; } 

现在，请求的代码，使用掩码将位数限制为6：

 unsigned int nextGray(unsigned int num) { return binaryToGray((grayToBinary(num) + 1) & 0x3F); } unsigned int prevGray(unsigned int num) { return binaryToGray((grayToBinary(num) - 1) & 0x3F); } 

Answer 2

根据定义，具有单个位改变的任何扰动都是有效的相邻格雷码。 问题是对于六位值，有六种可能的结果，在任何单一编码中只有两种可能是正确的结果。

随着单词大小的增加，非确定性会变得更糟。

Answer 3

最快的解决方案是将格雷码转换为常规二进制，获取下一个值并将值转换回格雷码。 这些操作可能是最快，也是最简单的操作。

否则，您可以使用以下操作：

 unsigned next_gray(unsigned gray) { if (is_gray_odd(gray)) { unsigned y = gray & -gray; return gray ^ (y << 1); } else { // Flip rightmost bit return gray ^ 1; } } 

如您所见，您必须知道格雷码的奇偶校验才能知道要应用哪种计算。 常规格雷码的奇偶校验与其设置位数的奇偶校验相同。 因此，计算is_gray_odd公式is_gray_odd ：

 bool is_gray_odd(unsigned gray) { for (size_t i = CHAR_BIT * sizeof(int) / 2u ; i ; i >>= 1u) { gray ^= (gray >> i); } return (bool)(gray & 1u); } 

函数previous_gray将与函数next_gray相同，除了您必须反转条件。 无论如何，前后转换到常规可能最终会更快。

编辑：如果您正在使用GCC或Clang，您可以使用编译器内在__builtin_parity来计算格雷码的奇偶校验（并可能检查是否存在__GNUC__和__clang__以保持跨平台）：

 bool is_gray_odd(unsigned gray) { return (bool) __builtin_parity(gray); } 

如果这样做，计算下一个/上一个格雷码可能比在某些架构上来回转换格雷码更快。 无论如何，如果你想要速度，你更好的基准。

编辑2：如果你只需要两个邻居而你不关心哪一个是前一个，哪个是下一个，你甚至不关心奇偶校验，你可以得到这两个：

 unsigned neighbour1 = gray ^ 1; unsigned neighbour2 = gray ^ ((gray & -gray) << 1);