c - 格雷码中的邻居

Question

有什么算法可以用来在格雷码中找到邻居吗？

对于小数字来说，写整个表格就可以了，但是如果我有一个像010 110这样的数字，用 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：

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