格雷码增量函数

Question

格雷码增量函数

cperformancealgorithmoptimizationgray-code

15

不使用任何外部计数器或其他状态，我正在寻找一个高效的函数，它接受一个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-entry LUT来快捷地处理最后的k个操作（一条评论建议使用k=32）。

另一种我想到的技术是乘法和位掩码的组合，这通常可以很快地简化事情。例如，计算奇偶校验以实现基于奇偶性的算法。

从乘法和位掩码的方法来看，似乎有空间发明一种进一步简化操作集的格雷码......但我想没有这样的代码是已知的。

- sh1

3

将灰度图像转换为二进制图像只需要 log(n) 步骤，而不是 n 步。例如：x ^= x >> 1; x ^= x >> 2; x ^= x >> 4; x ^= x >> 8; 等。 - harold

1

似乎《计算问题》（http://www.jjj.de/fxt/）第1.16.3章节（“在格雷码中递增（计数）”）提出的解决方案可能适用于此问题。 - Evgeny Kluev

如果您有很多内存（16GByte），只需创建一个数组int [2 ^ 32] gray2binary，其中使用grayCode作为索引，并将二进制代码作为数组条目的值。 ;-) - MrSmith42

4个回答

4

根据您的需求，我会选择三种不同的方式进行翻译。

1）共同函数：编写一个处理您需要支持的最广泛的Gray码值的单个函数。然后按照@harold建议的方法使用越来越大的移位和XOR操作：

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

扩展输入数据类型和移位操作，直到下一个移位量大于或等于数据位数为止。设置和测试甚至一个循环都比运行这些指令效率低。这将比查找方法略慢一点。

2) 每个二次幂的函数与上述方法相同，但具有graycodeToBinary_8、_16、_32版本。如果您需要进行许多小型转换并偶尔进行非常大的转换，则可以受益于此。如果使用C++过载，可以自动选择适当的版本（并且您可以通过一些模板元编程将其提高到荒谬水平）。

3) 查找表：这似乎是一个好主意，除非您考虑缓存行为。如果您不经常使用查找表，则与上述方法相比，它是不必要地复杂的。如果您经常使用查找表，它很可能会破坏您的缓存行为（对较大的内存区域进行大量分散的读取）。在一小部分应用程序中，这将变得非常稍微快一些。此外，您必须创建查找表，因此您可能已经可用graycode_to_binary函数。

最终，我很少发现除选项1）之外的任何用途。我见过一个嵌入式应用程序将查找表硬编码到其ROM中。由于处理器没有缓存，这很好。

- Speed8ump

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
        }
    }
}

- Willem Van Onsem

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

- user2746020

3

这种方法的唯一问题，正如问题和维基百科文章所述，就在于解码需要大量时间（与位数成线性关系）。 - Willem Van Onsem

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

一个简单的Gray码递增算法：

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的二进制位数。然而，在上述算法中的每一步都会改变奇偶性，所以在循环中可以交替使用偶校验和奇校验操作（当然，这违反了原帖要求不保留状态的要求，它需要一个比特的状态。另请参见下文）。

使用标准位操作即可在O(1)时间内找到y：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 不是最高位，则 y leftshift 1，否则 y。（在大多数体系结构中，测试可以是 if y leftshift 1 不等于0。）另外，您还可以在 y 太大无法左移时抛出异常或返回错误。