Gray code increment function

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 l