格雷碼

格雷碼是一種數字編碼方式，使得相鄰數字之間只有一個數字的差異為 1。“格雷碼”一詞通常用於指“反射”碼，更具體地說是指二進位制反射格雷碼。

要將二進位制數 轉換為其對應的二進位制反射格雷碼，從右側的數字 （第 個或最後一個數字）開始。如果 為 1，則將 替換為 ；否則，保持不變。然後繼續到 。繼續直到第一個數字 ，由於 被假定為 0，所以保持不變。結果數字 是反射二進位制格雷碼。

要將二進位制反射格雷碼 轉換為二進位制數，再次從第 位數字開始，並計算

如果 為 1，則將 替換為 ；否則，保持不變。接下來計算

等等。結果數字 是對應於初始二進位制反射格雷碼的二進位制數。

該程式碼被稱為反射碼，因為它可以透過以下方式生成。取格雷碼 0, 1。先正向寫，再反向寫：0, 1, 1, 0。然後在前半部分前面加上 0，後半部分前面加上 1：00, 01, 11, 10。繼續，寫 00, 01, 11, 10, 10, 11, 01, 00 得到：000, 001, 011, 010, 110, 111, 101, 100, ... (OEIS A014550)。因此，每次迭代都會使程式碼數量翻倍。

上面的圖表顯示了前 255 個（上圖）和前 511 個（下圖）格雷碼的二進位制表示。下表給出了對應於前幾個非負整數的格雷碼。

二進位制反射格雷碼與河內塔和中國環的解，以及超立方體圖的哈密頓環（包括方向反轉；Skiena 1990，第 149 頁）密切相關。