格雷码增量功能

本文介绍了格雷码增量功能的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

不使用任何外部计数器或其他状态，我正在寻找一个高效函数，它接受一个 n 位值(32 位左右)并在 格雷码.

Without using any external counters or other state, I'm looking for an efficient function which takes an n-bit value (32 bits or thereabouts) and returns the subsequent value in a 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) 迭代的循环).

But while the binary_to_gray() function is trivial (x ^ (x >> 1)), the corresponding gray_to_binary() is not so trivial at all (a loop of log(n) iterations).

也许有更高效的操作序列?要么是标准反射格雷码，要么是为解决这个问题而选择的另一个格雷码.

Perhaps there is a more efficient sequence of operations? Either for the standard reflected Gray code, or for another Gray code chosen to suit this problem.

旁白:对于这个问题，我看到了两种可能的解决方案——一种是选择一种更容易转换为二进制的代码，并使用上面给出的形式(或演示更有效的反射码转换为二进制)，另一种是完全推迟转换为二进制，并产生一种不使用二进制增量遍历格雷码的方法.

Aside: I see two possible solution types to this problem -- one is to choose a code that is easier to convert to binary and to use the form given above (or to demonstrate a more efficient conversion to binary for reflected codes), and the other is to defer conversion to binary altogether and to produce a method which walks through a gray code without the use of a binary increment.

在后一种情况下，将结果代码转换为二进制可能会特别困难.从实际角度来看，这可能是不利的一面，但它仍然是一件有趣的事情.

In the latter case, it might turn out to be especially difficult to convert the resulting code to binary. That's likely a down-side in practical terms, but it'd still be an interesting thing to see.

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

Update: Since it's been pointed out that the Gray decode is only log(n) operations (using either of two different techniques), I spent some time trying to figure out if that is a strict limit on how far things can be simplified. All bits must be considered when determining the next operation to perform, otherwise the 'considered' bits would fail to change and the function would oscillate between two values. The input must be compressed, in some way, to a manageable scale to determine the next operation to perform.

为了实现log(nk)操作，可以使用2k-entry LUT来缩短最后的k操作(评论建议 k=32).

To make it log(n-k) operations, a 2k-entry LUT could be used to short-cut the last k operations (a comment suggests k=32).

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

Another technique which came to mind which can often reduce things very quickly is a combination of multiplication and bitmasks. For example, to compute the parity in order to implement the parity-based algorithm.

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

From the multiply-and-bitmask approach, it seems like there might be space to invent a Gray code which simplifies the set of operations even further... but I don't imagine any such code is known.

推荐答案

一种简单的格雷码递增算法:

A simple algorithm for incrementing a gray code:

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 要求；它需要一位状态.另外，请参见下文.)

Finding the parity of x takes O(log(k)), where k is the bitlength of x. However, every step in the above algorithm changes parity, so in a loop you could just alternate the even and odd parity operations. (Of course, that fails the OP requirement that no state be kept; it requires one bit of state. Also, see below.)

使用标准位破解法找到 y 是 O(1):y = x&-x，其中 - 是 2 的补码取反运算符；你也可以把它写成 y = x 而不是 (x - 1).

Finding y is O(1) using a standard bit-hack: y = x&-x, where - is the 2's complement negate operator; you could also write it as y = x and not (x - 1).

您也可以使用奇偶增强型格雷码，即以逆奇偶校验位为后缀的格雷码(因此增强型码的奇偶校验始终为奇数).在这种情况下，您可以使用以下 O(1) 算法:

You also might be able to use the parity-enhanced gray code, which is the gray code suffixed with an inverse parity bit (so that the parity of the enhanced code is always odd). In that case you can use the following O(1) algorithm:

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

在上述两种算法中，为了清楚起见，我省略了溢出检查.为了使代码循环溢出，如果 y 不是高位，则将 y leftshift 1 替换为 y leftshift 1，否则为 y.(在大多数架构上，测试可以是 if y leftshift 1 is not 0.)或者，如果 y 太远，您可以抛出异常或返回错误大左移.

In both the above algorithms, I've left out the overflow check for clarity. To make the code cycle on overflow, replace y leftshift 1 with y leftshift 1 if y is not the high-order bit, else y. (On most architectures, the test could be if y leftshift 1 is not 0.) Alternatively, you could throw an exception or return an error in the event that y is too large to shift left.