LeetCode 格雷碼：二進制與格雷碼互轉演算法

題目描述

格雷碼是一種二進制編碼系統，任意兩個相鄰代碼僅有一位二進制數不同。給定非負整數 n（代表二進制位數），請生成 n 位格雷碼序列。序列必須以 0 開頭。

範例：

輸入: n = 2
輸出: [0, 1, 3, 2]
對應二進制:
00 - 0
01 - 1
11 - 3
10 - 2

解題思路：二進制轉格雷碼公式

根據維基百科定義，整數 i 對應的格雷碼為：

gray(i) = i ^ (i >> 1)

即：將 i 右移一位後與原值進行異或運算。對 i = 0 ~ 2^n - 1 依次應用此公式即可得到完整序列。

時間複雜度：O(2^n)，空間複雜度：O(2^n)（輸出本身大小）。

Python 參考實現

class Solution:
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        return [(i >> 1) ^ i for i in range(1 << n)]

# 測試
if __name__ == "__main__":
    assert Solution().grayCode(2) == [0, 1, 3, 2]
    assert Solution().grayCode(1) == [0, 1]
    assert Solution().grayCode(0) == [0]
    print("測試通過")

補充：格雷碼的遞歸構造法

除了公式法，格雷碼也可通過鏡像遞歸生成：

• n=1：[0, 1]
• n=k：在 n=k-1 序列前加 0，再將序列反轉並在前面加 1

這種方法更直觀地體現了「相鄰只差一位」的性質。

核心要點總結

• 核心公式：i ^ (i >> 1) 是二進制轉格雷碼的標準算法
• 位運算技巧：1 << n 快速計算 2^n
• 應用場景：格雷碼常用於旋轉編碼器、漢諾塔問題、基因演算法等

掌握這個簡潔的位運算公式，即可輕鬆解決格雷碼生成問題。