从第(n-1)个格雷码派生第n个格雷码 [英] Deriving nth Gray code from the (n-1)th Gray Code

问题描述

有没有办法通过对第(n-1)个格雷码进行位操作来使用第(n-1)个格雷码导出第4位第n个格雷码?

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?

例如，第4个格雷码是0010.现在，我想通过对0010进行位运算来获得第5个格雷码0110.

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

推荐答案

也许是作弊"，但您可以将查找表打包成64位常量值，如下所示:

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

或者，您可以使用公式将灰色转换为二进制，递增该值，然后从二进制转换为灰度，即n xor(n/2):

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);
}

这篇关于从第(n-1)个格雷码派生第n个格雷码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！