bit-manipulationgray-code

Deriving nth Gray code from the (n-1)th Gray Code


Is there a way to derive the 4-bit nth Gray code using the (n-1)th Gray code by using bit operations on the (n-1)th Gray Code?

For example the 4th Gray code is 0010. Now I want to get the 5th Gray Code, 0110, by doing bit operations on 0010.


Solution

  • Perhaps it's "cheating" but you can just pack a lookup table into a 64-bit constant value, like this:

    0000 0 -> 1
    0001 1 -> 3
    0011 3 -> 2
    0010 2 -> 6
    0110 6 -> 7
    0111 7 -> 5
    0101 5 -> 4
    0100 4 -> C
    1100 C -> D
    1101 D -> F
    1111 F -> E
    1110 E -> A
    1010 A -> B
    1011 B -> 9
    1001 9 -> 8
    1000 8 -> 0
    
    FEDCBA9876543210 nybble order (current Gray code)
    |              |
    V              V
    EAFD9B80574C2631 next Gray code
    

    Then you can use shifts and masks to perform a lookup (depending on your language):

    int next_gray_code(int code)
    {
         return (0xEAFD9B80574C2631ULL >> (code << 2)) & 15;
    }
    

    Alternatively, you can use the formula for converting from Gray to binary, increment the value, and then convert from binary to Gray, which is just n xor (n / 2):

    int next_gray_code(int code)
    {
        code = code ^ (code >> 2);
        code = code ^ (code >> 1);
        code = (code + 1) & 15;
        return code ^ (code >> 1);
    }