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.

Piscatelli

Converting from gray to binary should only take log(n) steps, not n. Like x ^= x >> 1; x ^= x >> 2; x ^= x >> 4; x ^= x >> 8; etc. – Lubin

It seems "Matters Computational", chapter 1.16.3 ("Incrementing (counting) in Gray code") proposes a solution that may be suitable for this problem. – Screw

If you have a lot of memory (16GByte), simply make an array int[2^32] gray2binary where you use the grayCode as index and get the binary code as value of the arrayEntry. ;-) – Imputable

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.

Subbasement

Sorry for the late comment. I don't get this answer. First, what does it mean to shift left the right most 1 bit? in other words, what is 'y'? A word with a bit set only in the position corresponding to the rightmost set bit of x? Moreover, What does x xor 1 mean? Does it mean to xor x with a word consisting of the bit pattern of the number one (i.e. all zeros except the first)? In that case, what is that xor supposed to do? afaik it would flip all the bits except the first. How can this lead to the next gray code? – Maciemaciel

@gigabytes: by "the rightmost 1 bit" I meant the word formed by setting to 0 everything except the rightmost 1 bit. (Eg if the original were in binary 100101000, then the rightmost 1 bit would be 000001000 and that value leftshifted by 1 would be 0000010000.) xor with 1 flips the low-order bit and leaves the other ones untouched; I think you have the definition of xor inverted. – Subbasement

Yes, I've inverted the definition, sorry. I'm still missing something, though. Why in case of even parity it is sufficient to flip the lsb? I think I'm missing the whole point. Can you point me to a resource that explain a little bit the reason behind this code? – Maciemaciel

@gigabytes: The point is to flip exactly one bit on every iteration. This algorithm flips bit i (counting from the low-order bit) every 2^(i+1) steps, with the first flip at iteration 2^i. It's pretty easy to prove that doing that will cycle through all bit patterns. (Induction on length of code.) It's also (fairly) simple to derive the algorithm from that description, which is how I got the algorithm; I can't speak for all the other people who have figured it out. – Subbasement

So this is "one" gray code or "the" gray code? (I mean the original "inverted binary code") – Maciemaciel

@gigabytes: It's the same Gray code as the question. But of course there are many gray codes. – Subbasement

Answer 2

There are three ways I'd go with this depending on what you are after.

1) one common function: Write a single function that handles the widest possible graycode value you need to support. The follow the method that @harold suggested using ever greater shifts and xors:

inline UInt16 graycodeToBinary( UInt16 value )
{
    value ^= (value >> 1);
    value ^= (value >> 2);
    value ^= (value >> 4);
    value ^= (value >> 8);
    return value;
}

extend the input data type and the shifts as needed until the next shift amount would equal or exceed the number of data bits. Setting up and testing even one loop will be less efficient than running these instructions. This will be only slightly slower than a lookup method.

2) function per power of two Same as above but with graycodeToBinary_8, _16, _32 versions. Can be of benefit if you do lots of small conversions and the occasional very large one. If using C++ overloading can automatically choose the appropriate version for you (and you can turn it up to ridiculous with some template metaprogramming).

3) lookup table: This seems like a good idea unless you consider cache behaviors. If you are not using the lookup table very often, then it's needlessly complex versus the above method. If you are using the lookup table often it will likely wreck your cache behavior (lots of scattered reads to a larger region of memory). There is a small slice of applications where this will turn out to be very slightly faster. Also, you have to create the lookup table, so you're likely to have the function for graycode_to_binary already available.

In the end I've rarely found a use for anything but option 1). I've seen one embedded application which hard-coded the lookup table into it's ROM. That was fine since the processor didn't have cache anyway.

Dogmatic

Answer 3

I've implemented an algorithm in C# that seems to work:

First you need the parity of the integer. I've implemented it for a ulong (64-bit), but you can easily modify it to any desired output:

public static ulong GetParity (ulong value) {
    value ^= value >> 0x20;
    value ^= value >> 0x10;
    value ^= value >> 0x08;
    value ^= value >> 0x04;
    value &= 0x0f;
    return (0x6996UL >> (int)value) & 0x01;
}

Next you need to check if the parity is even (the number of bits set is even, if this is the case, you simply swap the last bit). If the parity is odd, you normally swap the bit on the left of the least significant set bit. This can be calculated with the following method:

public static ulong LeastSignificantBit (ulong value) {
    return value&((~value)+0x01);
}

There is one border case: if the least significant set bit, is the greatest bit of your Gray code, if that is the case, you can of course not swap the left bit, and you simply set your counter to zero.

To summarize, you can use the following code:

public static ulong GrayIncrement (ulong original, int bits = 0x40) {
    ulong last = 0x01UL << (bits - 0x01);
    if (GetParity (original) == 0x00) {
        return original ^ 0x01UL;//even parity: swap least significant bit
    } else {
        ulong lbm = LeastSignificantBit(original);
        if (lbm < last) {
            return original ^ (lbm << 0x01);//otherwise swap the bit left to the least significant set bit
        } else {
            return 0x00;//wrap around
        }
    }
}

Umbrage

Answer 4

From wiki (http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code)

/*
    The purpose of this function is to convert an unsigned
    binary number to reflected binary Gray code.

    The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}

/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}

Trilbee

The only problem with this approach, as stated both in the question and the wiki article is that decoding takes a large amount of time (here linear with the number of bits)... – Umbrage