c - Gray code increment function

Question

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.

That is:

int fn(int x)
{
    int y = gray_to_binary(x);
    y = y + 1;
    return binary_to_gray(y);
}

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.

---

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.

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.

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.

Answer 1

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)

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

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

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)

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.