Python格雷编码
困难3数字世界的“一步之遥”——Python格雷编码
你有没有想过，为什么数字世界里的“邻居”有时会隔着一条大沟？比如3（二进制011）和4（二进制100），明明只差1，二进制却每位都不同。如果信号传输中出了一点小差错，3可能变成7（111），这可就大错特错了！为了让相邻数字的二进制表示只有一位不同，人们发明了格雷编码（Gray Code）。它是一种特殊的二进制编码，任何两个相邻的数字，它们的二进制表示只有一位不同，就像环形跑道上相邻的两个点只差一步。这种编码在通信、旋转编码器、游戏（如汉诺塔）中广泛使用，能有效减少传输错误。
什么是格雷编码？从日常说起
想象一个圆形操场，上面标着0到7八个位置。你从0走到1，只需要迈出一小步；从1走到2，也是一小步。但如果用普通二进制编码，从3（011）走到4（100）需要跨过三步（每一位都变），很容易“摔跤”。格雷编码就像在操场上画了八个相邻的小格子，每两个格子之间只差一个台阶，走起来稳稳当当。
普通二进制和3位格雷码对比：
| 十进制 | 二进制 | 格雷码 |
|---|---|---|
| 0 | 000 | 000 |
| 1 | 001 | 001 |
| 2 | 010 | 011 |
| 3 | 011 | 010 |
| 4 | 100 | 110 |
| 5 | 101 | 111 |
| 6 | 110 | 101 |
| 7 | 111 | 100 |
看到没？格雷码的相邻两行（如010→110）只有左起第一位不同，而二进制中010→011却是最后一位不同。这正是格雷编码的核心：相邻数字仅一位变化。
为什么需要格雷编码？
生活中的一个例子：你和小伙伴玩“猜数字”游戏，你们用二进制信号传递数字。普通二进制下，从3跳到4时，信号需要同时翻转三个灯泡，如果灯泡有延时或错误，可能变成其他数字。而用格雷码，每次只翻转一个灯泡，即使信号有点干扰，也只能变成相邻的数字，不会差太远。所以在数字通信和旋转编码器（比如鼠标滚轮、音量旋钮）中，格雷编码能大大降低出错概率。
如何生成格雷编码？公式法和递归法
公式法：i XOR (i>>1)
生成n位格雷码有一个简单公式：
第i个格雷码 = i XOR (i >> 1)
其中 XOR 是按位异或，>> 是右移一位。
比如 i=3（二进制011）时：
- i>>1 = 001
- 011 XOR 001 = 010（十进制2），正好对应上表中序号3的格雷码。
递归法：从n-1位格雷码构造n位
另一种直观方法：
- n=0时，只有[0]
- n=1时，格雷码：[0, 1]（二进制0和1，只有一位不同）
- 想得到n位格雷码，先得到n-1位格雷码列表，然后：
- 在列表前每一位前面加0（即原样保留）
- 把列表倒序，并在每一位前面加1（即最高位置1，加上
1 << (n-1)）
这样相邻的格雷码之间仍然只有一位不同。
Python代码实现：两种方法完整写出来
下面代码用两种方法生成n位格雷码，并打印出二进制形式。注意变量名用简短英文，每行加中文注释。
# 方法1：使用公式生成格雷码
def gray_code_formula(n):
"""
返回n位格雷码的十进制列表，长度为2^n
"""
result = []
for i in range(1 << n): # 循环0到2^n-1
gray = i ^ (i >> 1) # 公式：i XOR (i>>1)
result.append(gray) # 将生成的格雷码添加到列表
return result
# 方法2：递归生成格雷码
def gray_code_recursive(n):
if n == 0: # 边界条件：0位格雷码只有[0]
return [0]
prev = gray_code_recursive(n - 1) # 先得到n-1位的格雷码列表
result = prev.copy() # 第一部分：前面加0（不变）
for code in reversed(prev): # 倒序遍历n-1位列表
result.append(code | (1 << (n - 1))) # 第二部分：最高位置1
return result
# 测试3位格雷码
n = 3
print(f"{n}位格雷码（十进制）：")
codes = gray_code_formula(n)
for i, val in enumerate(codes):
binary = format(val, f'0{n}b') # 将十进制数转为n位二进制字符串
print(f"序号 {i:2d} -> 格雷码 {binary}")
print("\n递归方法结果相同：", gray_code_recursive(n))
运行后你会看到输出：
3位格雷码（十进制）：
序号 0 -> 格雷码 000
序号 1 -> 格雷码 001
序号 2 -> 格雷码 011
序号 3 -> 格雷码 010
序号 4 -> 格雷码 110
序号 5 -> 格雷码 111
序号 6 -> 格雷码 101
序号 7 -> 格雷码 100
检查相邻序号，确实只有一位不同。
新手容易犯的错误
-
忘记处理n=0的情况
递归方法中如果n=0直接返回[0]是必须的，否则会无限递归。公式法也需要保证1 << n有意义（n=0时循环范围是0到0）。 -
递归时倒序写错
有些同学会写成for code in prev[::-1]但忘记复制原列表，其实可以用reversed(prev)更清晰。注意第二部分必须加最高位，不是加前导0。 -
混淆二进制和格雷码的转换
格雷码是编码，不是二进制数值本身。公式i ^ (i>>1)中i是序号（0~2^n-1），不是二进制值。初学者可能会误把格雷码当二进制直接运算。
完整可运行的示例程序
将上面的代码整合成一个文件，再加一个主函数，方便直接运行查看不同位数：
"""
格雷编码生成器 —— 展示两种方法
"""
def gray_code_formula(n):
"""公式法生成n位格雷码"""
result = []
for i in range(1 << n):
gray = i ^ (i >> 1)
result.append(gray)
return result
def gray_code_recursive(n):
"""递归法生成n位格雷码"""
if n == 0:
return [0]
prev = gray_code_recursive(n - 1)
result = prev.copy()
for code in reversed(prev):
result.append(code | (1 << (n - 1)))
return result
def print_gray_codes(n, codes):
"""打印n位格雷码的十进制和二进制"""
print(f"{n}位格雷码（共{len(codes)}个）：")
for i, val in enumerate(codes):
binary = format(val, f'0{n}b')
print(f"序号 {i:2d} -> 十进制 {val:3d} -> 二进制 {binary}")
# 主程序：测试不同位数
for n in range(1, 5):
print("\n" + "="*30)
codes1 = gray_code_formula(n)
codes2 = gray_code_recursive(n)
# 两种方法结果应该一致
assert codes1 == codes2, f"两种方法结果不一致！n={n}"
print_gray_codes(n, codes1)
运行结果会展示1到4位的格雷码，你可以验证相邻的二进制只有一位不同。
相关知识点延伸
- 位运算：公式
i ^ (i>>1)涉及异或和右移，是Python位运算的基础应用。了解&、|、^、<<、>>能帮你写出高效的代码。 - 递归思想：递归法将大问题分解为小问题，是计算机科学的重要思维。可以对比汉诺塔、斐波那契数列的递归写法。
- 汉诺塔与格雷码：经典的汉诺塔游戏最优解中，每一步移动的圆盘编号恰好遵循格雷码顺序。如果你玩过汉诺塔，会发现格雷码能帮你记住下一步该移动哪个盘子。
- 旋转编码器：很多机械旋钮（如音量旋钮、鼠标滚轮）内部使用格雷码盘，每次旋转一格只改变一位，确保读数和实际位置一致。
格雷编码虽然是一个小巧的数学概念，但在数字世界里却像一座坚实的桥梁，让相邻的数字安全地“握手”。动手运行上面的代码，观察不同位数的格雷码，你会发现它们真的就像环形跑道上的台阶——每一步都踏实稳妥。
例题精讲
在格雷编码中，相邻两个码字的二进制位差异个数是？
在n位循环格雷编码中，第一个码字和最后一个码字之间恰好有一个二进制位不同。
以下函数将自然二进制数（整数）转换为对应的格雷码（整数），请补全空缺处的表达式。
def binary_to_gray(n):
return ___以下关于格雷编码的说法，错误的是？
以下递归函数用于生成n位格雷码的二进制字符串列表（如n=2时返回["00","01","11","10"]），请补全空缺处的代码。
def gray_code(n):
if n == 0:
return [""]
prev = gray_code(n-1)
result = []
for code in prev:
result.append("0" + code)
for code in ___ :
result.append("1" + code)
return result