c - 格雷码递增函数

Question

在不使用任何外部计数器或其他状态的情况下，我正在寻找一个高效函数，该函数采用 n 位值(32 位左右)并返回 Gray code 中的后续值。 .

即:

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

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

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

Answer 1

递增格雷码的简单算法:

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 而不是 (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，否则 y。 (在大多数架构中，测试可能是 if y leftshift 1 is not 0。)或者，如果 y 太小，您可以抛出异常或返回错误大到左移。