13

在不使用任何外部计数器或其他状态的情况下，我正在寻找一个有效的函数，它采用 n 位值（32 位或左右）并以格雷码返回后续值。

那是：

int fn(int x)
{
    int y = gray_to_binary(x);
    y = y + 1;
    return binary_to_gray(y);
}

但是，虽然binary_to_gray()函数是微不足道的 ( x ^ (x >> 1))，但对应的函数gray_to_binary()一点也不微不足道（log(n)迭代循环）。

也许有更有效的操作顺序？无论是标准反射格雷码，还是选择适合此问题的另一个格雷码。

另外： 我看到这个问题有两种可能的解决方案类型——一种是选择一个更容易转换为二进制的代码并使用上面给出的形式（或者演示一个更有效的反射代码到二进制的转换），以及另一种是完全推迟到二进制的转换，并产生一种在不使用二进制增量的情况下遍历格雷码的方法。

在后一种情况下，将生成的代码转换为二进制可能特别困难。实际上，这可能是不利的一面，但这仍然是一件有趣的事情。

更新： 由于有人指出格雷解码只是log(n)操作（使用两种不同技术中的任何一种），我花了一些时间试图弄清楚这是否是对事情可以简化的严格限制。在确定要执行的下一个操作时，必须考虑所有位，否则“考虑”位将无法更改，并且函数将在两个值之间振荡。输入必须以某种方式压缩到可管理的规模，以确定下一个要执行的操作。

为了使其log(n-k)操作，可以使用 2 k条目 LUT 来缩短最后的k操作（评论建议k=32）。

我想到的另一种通常可以非常快速地减少事物的技术是乘法和位掩码的组合。例如，计算奇偶校验以实现基于奇偶校验的算法。

从乘法和位掩码方法来看，似乎可能有空间发明格雷码，它可以进一步简化操作集......但我不认为有任何这样的代码是已知的。

4

4 回答 4

11

增加格雷码的简单算法：

gray_inc(x):
  if parity of x is even:
    return x xor 1
  if parity of x is odd:
    let y be the rightmost 1 bit in x
    return x xor (y leftshift 1)

找到 x 的奇偶校验需要 O(log(k))，其中 k 是 x 的位长。然而，上述算法中的每一步都会改变奇偶校验，所以在一个循环中你可以交替奇偶校验操作。（当然，这不符合 OP 的要求，即不保留任何状态；它需要一位状态。另外，请参见下文。）

使用标准 bit-hack: 找到 y 是 O(1) y = x&-x，其中-2 的补码取反运算符；你也可以把它写成y = x and not (x - 1).

您还可以使用增强奇偶校验的格雷码，它是后缀为逆奇偶校验位的格雷码（因此增强码的奇偶校验总是奇数）。在这种情况下，您可以使用以下 O(1) 算法：

parity_gray_increment(x):
  let y be the rightmost bit in x
  return x xor ((y leftshift 1) or 1)

在上述两种算法中，为了清楚起见，我都省略了溢出检查。要使代码在溢出时循环，请替换y leftshift 1为y leftshift 1 if y is not the high-order bit, else y. （在大多数架构上，测试可能是.）或者，如果太大而无法左移if y leftshift 1 is not 0，您可以抛出异常或返回错误。y

于 2013-07-05T16:23:38.537 回答
4

根据您的需求，我会采用三种方法。

1）一个通用函数：编写一个函数来处理您需要支持的最广泛的灰度代码值。遵循@harold 建议使用更大的移位和异或的方法：

inline UInt16 graycodeToBinary( UInt16 value )
{
    value ^= (value >> 1);
    value ^= (value >> 2);
    value ^= (value >> 4);
    value ^= (value >> 8);
    return value;
}

根据需要扩展输入数据类型和移位，直到下一个移位量等于或超过数据位数。设置和测试即使是一个循环也比运行这些指令效率低。这只会比查找方法稍微慢一点。

2) 每 2 次幂的函数 同上，但有 graycodeToBinary_8、_16、_32 版本。如果您进行大量小型转换并且偶尔进行非常大的转换，这可能会有所帮助。如果使用 C++ 重载可以自动为您选择合适的版本（并且您可以通过一些模板元编程将其变得可笑）。

3) 查找表：这似乎是个好主意，除非您考虑缓存行为。如果您不经常使用查找表，那么与上述方法相比，它不必要地复杂。如果您经常使用查找表，它可能会破坏您的缓存行为（大量分散读取到更大的内存区域）。有一小部分应用程序会变得非常快。此外，您必须创建查找表，因此您可能已经拥有 graycode_to_binary 的功能。

最后，除了选项 1) 之外，我很少发现其他任何用途。我见过一个嵌入式应用程序将查找表硬编码到它的 ROM 中。这很好，因为处理器无论如何都没有缓存。

于 2013-07-05T18:04:57.057 回答
2

我在 C# 中实现了一个似乎可行的算法：

首先，您需要整数的奇偶性。我已经为ulong（64 位）实现了它，但您可以轻松地将其修改为任何所需的输出：

public static ulong GetParity (ulong value) {
    value ^= value >> 0x20;
    value ^= value >> 0x10;
    value ^= value >> 0x08;
    value ^= value >> 0x04;
    value &= 0x0f;
    return (0x6996UL >> (int)value) & 0x01;
}

接下来您需要检查奇偶校验是否为偶数（设置的位数是偶数，如果是这种情况，您只需交换最后一位）。如果奇偶校验是奇数，您通常交换最低有效设置位左侧的位。这可以通过以下方法计算：

public static ulong LeastSignificantBit (ulong value) {
    return value&((~value)+0x01);
}

有一个边界情况：如果最低有效位是格雷码的最高位，如果是这种情况，你当然不能交换左边的位，你只需将计数器设置为零。

总而言之，您可以使用以下代码：

public static ulong GrayIncrement (ulong original, int bits = 0x40) {
    ulong last = 0x01UL << (bits - 0x01);
    if (GetParity (original) == 0x00) {
        return original ^ 0x01UL;//even parity: swap least significant bit
    } else {
        ulong lbm = LeastSignificantBit(original);
        if (lbm < last) {
            return original ^ (lbm << 0x01);//otherwise swap the bit left to the least significant set bit
        } else {
            return 0x00;//wrap around
        }
    }
}
于 2014-07-08T08:48:42.293 回答
1

来自维基（http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code）

/*
    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;
}
于 2014-07-08T13:38:48.030 回答