The neighbors in Gray code

问题:

Is there any algorithm that I can use to find the neighbors in Gray code?

For small numbers is just fine to write the entire table, but if I have a number like 010 110 is a bit to much to write the entire grey code table with 6 numbers.

回答1:

Copied shamelessly from Wikipedia:

/*
        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;
}

And now, the requested code, using the mask to limit the number of bits to 6:

unsigned int nextGray(unsigned int num)
{
    return binaryToGray((grayToBinary(num) + 1) & 0x3F);
}

unsigned int prevGray(unsigned int num)
{
    return binaryToGray((grayToBinary(num) - 1) & 0x3F);
}

回答2:

By definition, any perturbation with a single bit change is a valid adjacent Gray code. The problem is that for a six bit value there are six possible results and only two of them can be the correct one in any single coding.

The non-determinism gets worse as you increase the word size.

回答3:

The fastest solution is to convert the gray code to regular binary, get the next value and convert the value back to gray code. Those operations are probably the fastest and the simplest you could get.

Otherwise, you can use the following operation:

unsigned next_gray(unsigned gray)
{
    if (is_gray_odd(gray))
    {
        unsigned y = gray & -gray;
        return gray ^ (y << 1);
    }
    else
    {
        // Flip rightmost bit
        return gray ^ 1;
    }
}

As you can see, you have to know the parity of the gray code in order to know which computation to apply. The parity of a regular gray code is the same as the parity of its number of set bits. Hence the following formula to compute is_gray_odd:

bool is_gray_odd(unsigned gray)
{
    for (size_t i = CHAR_BIT * sizeof(int) / 2u ; i ; i >>= 1u)
    {
        gray ^= (gray >> i);
    }
    return (bool)(gray & 1u);
}

The function previous_gray will be the same as the function next_gray, except that you have to reverse the condition. Anyway, the back and forth conversion to regular may eventually be faster.

EDIT: if you are using GCC or Clang, you can use the compiler intrinsic __builtin_parity to compute the parity of a gray code (and possibly check for the existence of __GNUC__ and __clang__ to remain cross-platform):

bool is_gray_odd(unsigned gray)
{
    return (bool) __builtin_parity(gray);
}

If you do so, computing the next/previous gray code can be faster than converting the gray code back and forth to binary on some architectures. Anyway, if you want speed, you better benchmark.

EDIT 2: If you only need the two neighbours and you don't care about which is the previous one and which is the next one, they you don't even care about the parity, you can get both of them like this:

unsigned neighbour1 = gray ^ 1;
unsigned neighbour2 = gray ^ ((gray & -gray) << 1);