格雷码递增函数

Question

不使用任何外部计数器或其他状态,我正在寻找一个有效的函数,它取一个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).

另一种可以经常减少事物的技术是乘法和位掩码的组合.例如,计算奇偶校验以实现基于奇偶校验的算法.

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

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 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太大而无法向左移动的情况下返回错误.