bit-manipulation - (n-1) 番目のグレイ コードから n 番目のグレイ コードを導出する

Question

(n-1) 番目のグレイ コードのビット操作を使用して、(n-1) 番目のグレイ コードを使用して 4 ビットの n 番目のグレイ コードを導出する方法はありますか?

たとえば、4 番目のグレイ コードは 0010 です。今度は、0010 に対してビット演算を実行して、5 番目のグレイ コード 0110 を取得したいと考えています。

Answer 1

おそらく「不正行為」ですが、次のように、ルックアップ テーブルを 64 ビットの定数値にパックすることができます。

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

次に、シフトとマスクを使用してルックアップを実行できます (言語によって異なります)。

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

または、 Gray から binaryに変換する式を使用し、値をインクリメントしてから、n xor (n / 2) であるバイナリから Gray に変換できます。

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