LeetCode 89. 格雷编码
本节目标
用 i ^ (i >> 1) 直接构造相邻编码恰好一位不同的循环序列。
格雷编码把连续编号映射为相邻仅一位不同的二进制串。这是位运算拓展中“构造不变量”框架的一个直接应用：不搜索下一项，而是由每个编号一次算出它的位置。
题意与约束
给定非负整数 n，返回一个长度为 2^n 的整数序列。序列中的每个数都在 [0, 2^n) 内，任意相邻两项的二进制表示恰好一位不同；最后一项与第一项也必须满足同一条件。
1 <= n <= 16。- 序列从
0开始。 - 题目允许多种有效答案；这里构造标准的二进制反射格雷码顺序。
从二进制编号构造格雷码
按编号 i = 0, 1, ..., 2^n - 1 依次计算：
gray(i) = i ^ (i >> 1)
二位编号的映射如下：
i | 二进制 i | i >> 1 | gray(i) |
|---|---|---|---|
0 | 00 | 00 | 00 |
1 | 01 | 00 | 01 |
2 | 10 | 01 | 11 |
3 | 11 | 01 | 10 |
因此得到 00, 01, 11, 10，相邻项依次只翻转最低位、次低位、最低位。
为什么 i ^ (i >> 1) 有效
相邻的二进制编号 i 与 i + 1 会因为进位改变一段连续后缀：若末尾有若干个 1，它们会变为 0，紧邻它们左侧的 0 变为 1。也就是说，编号的变化不是通常只改一位，而是一段连续位同时改变。
在 i ^ (i >> 1) 中，右移结果的第 k 位来自原数第 k + 1 位；按通常从高位写到低位的二进制记法，就是每一位都与它左边相邻的更高位比较。连续后缀内部的两个相邻位会一起翻转，异或结果不变；只有这段变化的边界会留下一个不同的位。因此连续的 gray(i) 与 gray(i + 1) 恰好相差一位。
此外，异或变换可逆：从高位到低位逐位恢复 i，所以不同的编号不会映射到同一个格雷码。遍历全部 2^n 个编号便恰好得到范围内的全部编码。
首尾相邻条件
第一项是 gray(0) = 0。最后一个编号为 2^n - 1，它的低 n 位全为 1；右移一位后低 n - 1 位为 1。两者异或后只剩最高的第 n - 1 位，即 gray(2^n - 1) = 2^(n - 1)。
它与 0 的异或正好是一个二进制单比特，因此最后一项与第一项同样只相差一位，序列构成环。
代码实现
C++ 和 Python 都直接遍历编号并计算 i ^ (i >> 1)，无需递归、回溯或维护已生成序列。
- C++
- Python
#include <vector>
using namespace std;
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> answer;
for (int i = 0; i < (1 << n); i++) {
answer.push_back(i ^ (i >> 1));
}
return answer;
}
};
class Solution:
def grayCode(self, n: int) -> list[int]:
return [i ^ (i >> 1) for i in range(1 << n)]
复杂度分析
需要生成 2^n 个结果，每项只做常数次位运算，时间复杂度为 O(2^n)。返回数组本身占用 O(2^n) 空间，除结果外只使用常数额外空间。
易错点
- 写成
i ^ (i << 1)：移位方向错误，不能得到标准格雷码顺序。 - 只检查相邻项，不检查最后一项与
0：题目要求的是循环序列。 - 把普通二进制递增序列当作格雷码：进位可能同时改变多位，例如
01到10改变两位。 - 用回溯搜索所有排列：本题已有直接构造公式，搜索既更慢也更难证明覆盖完整。
模式迁移
遇到“连续状态的变化必须局部化”的构造题时，先观察原始编号变化会在哪一段扩散，再寻找能让段内变化相互抵消的相邻位关系。本题的右移异或正好把连续后缀的翻转压缩为边界的一位；这一思路可与位运算拓展中的二进制结构和构造不变量一起使用。