灰色code增值功能 [英] Gray code increment function

问题描述

无需使用任何外部柜台或其他国家，我正在寻找一个的有效的函数，该函数的n位值（32位或左右），并返回随后的值在的灰色code 。

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＆GT;＆GT; 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).

或许有操作的更高效的序列？无论是标准的体现灰色code，或选择适合这个问题的另一个灰色code。

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.

旁白：我看到两种可能的解决方案类型这个问题 - 一个是选择code更易于转换为二进制，并使用上面给出的形式（或证明一个更有效地转化为二进制为反射codeS），和另一种是推迟转换为二进制共和，以产生一种方法，它走过一个灰色code，而无需使用一个二进制增量

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.

在后一种情况下，它可能变成是特别难以转化所得code键二进制。这可能是一个不利的方面在实践中，但它还是会成为一个有趣的事情，看看。

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.

更新：由于它已经指出，灰色德code仅的log（n）操作（使用两种不同的技术），我花了一些时间，试图弄清楚，如果这是在多远的东西可以被简化了严格的限制。确定下一操作以执行时，否则视为位将不能改变，则该函数将两个值之间振荡的所有位必须加以考虑。输入必须是玉米pressed，以某种方式，在可管理的规模来决定下一个要执行的操作

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.

要使它日志（NK）操作，2 ^K -entry LUT可以用于短切过去 K 操作（一个意见建议 K = 32 ）。

To make it log(n-k) operations, a 2^k-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.

从乘法位掩码的方式，看起来有可能的空间来创造一个灰色code，简化了操作集更进一步......但我无法想象任何此类code是已知的。

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.

推荐答案

一个简单的算法递增灰色code：

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（日志（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).

您可能还可以使用奇偶增强灰色code，它是灰色的code后缀逆校验位（这样的增强code奇偶总是奇） 。在这种情况下，你可以使用下面的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)

在上述两种算法，我已经离开了溢出检查清楚。如果要对溢出的code周期，更换Ÿleftshift 1 与Ÿleftshift 1，如果y是不是高位，否则ÿ 。 （在多数平台上，测试可能是如果y leftshift 1不是0 ）。或者，你可以抛出一个异常或事件返回一个错误的是太大，无法左移。

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.

这篇关于灰色code增值功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！