京公网安备11010502063487号n 位格雷码序列是一个包含 2^n 个整数的序列，要求：每个整数在 0 到 2^n - 1 之间，第一个整数是 0，整数各不相同，相邻两个整数的二进制表示恰好只有一位不同，并且最后一个整数与第一个整数（首尾）也恰好只有一位不同。满足要求的序列不止一种，题目只要求返回任意一个。有一个漂亮的公式：第 i 个格雷码等于 i ^ (i >> 1)，也就是 i 与它自己右移一位再异或。本文不仅用镜像反射法（另一种独立的构造）验证这个公式的输出，还直接检查了题目要求的每一条性质，并对比一个看似相近的错误公式，给出五种语言的实现，并把逐个生成的过程做成分步演示。
完整题目见官方页面（链接在文末）。因为合法的答案不止一种，评测通常用检查器判定；本文的用例逐项对比的是 solve 与镜像反射法得到的同一个序列（两种构造得到的是同一个标准格雷码序列，下面的实验会验证），同时单独检查了题目要求的各条性质。基准解是镜像反射法：已有 n-1 位的序列，把它倒过来再写一遍，并在这一半的每个数最高位加 1。一共 10 组用例，n 取 1 到 6、8、10、12、16：
输入 [1] 输出 [0,1] 输入 [2] 输出 [0,1,3,2] 输入 [3] 输出 [0,1,3,2,6,7,5,4] 输入 [4] 输出 [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8] 输入 [5] 输出 [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16] 输入 [6] 输出 [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,41,43,42,46,47,45,44,36,37,39,38,34,35,33,32]
因为公式看起来很神奇，我直接对输出检查了题目的每一条要求：长度是不是 2^n、是否以 0 开头、是否互不相同、相邻（含首尾）是否恰好差一位，以及与镜像反射法的结果是否完全相同。最后一行对照了一个把右移写成左移的错误公式：
对 n 从 1 到 16 检查题目要求的每一条性质（对 solve 的输出逐项检查）： n= 1: 长度 2 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True n= 2: 长度 4 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True n= 3: 长度 8 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True n= 4: 长度 16 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True n= 8: 长度 256 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True n=12: 长度 4096 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True n=16: 长度 65536 = 2^n：True；以 0 开头：True；互不相同：True；相邻恰好差一位（含首尾）：True；与镜像反射法结果完全相同：True 对照：把公式写成 i ^ (i << 1)（左移），n 从 1 到 7 里有 6 个 n 不满足性质：[2, 3, 4, 5, 6, 7]
n 取 1、2、3、4、8、12、16 时，i ^ (i >> 1) 的输出五条检查全部通过，并且与镜像反射法的结果完全相同（65536 个数的序列也一样）。把公式写成 i ^ (i << 1)（左移，并截断到 n 位）：n 从 1 到 7 里有 6 个（n = 2 到 7）不满足性质，只有 n = 1 碰巧对。所以是"右移"，不是"左移"。
i 变成 i + 1 时，二进制的变化是：末尾连续的若干个 1 变成 0，紧挨着的那个 0 变成 1。右移一位之后，i >> 1 也发生了类似的变化，但整体错开一位。两者异或时，除了最高的那个变化位，其余变化位都被抵消了，所以相邻两个格雷码只有一位不同。这只是直觉，本文没有给出严格证明，上面的实验才是验证依据（n 到 16）。
对 i 从 0 到 2^n - 1，第 i 个格雷码就是 i ^ (i >> 1)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，五种语言的代码只有一行核心公式，1 << n 在 n 很大时要注意各语言整数的位数（题目 n 不超过 16，所以 32 位整数足够）。
Python · 解法代码def solve(n): return [i ^ (i >> 1) for i in range(1 << n)] # 第 i 个格雷码 = i 与「i 右移一位」的异或
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [1] → [0,1] [2] → [0,1,3,2] [3] → [0,1,3,2,6,7,5,4] [4] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8] [5] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16] [6] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,41,43,42,46,47,45,44,36,37,39,38,34,35,33,32]
Java · 解法代码class Solution { public List<Integer> grayCode(int n) { List<Integer> res = new ArrayList<>(); for (int i = 0; i < (1 << n); i++) res.add(i ^ (i >> 1)); // 第 i 个格雷码 = i 与「i 右移一位」的异或 return res; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [1] → [0,1] [2] → [0,1,3,2] [3] → [0,1,3,2,6,7,5,4] [4] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8] [5] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16] [6] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,41,43,42,46,47,45,44,36,37,39,38,34,35,33,32]
Go · 解法代码func grayCode(n int) []int { res := make([]int, 0, 1<<n) for i := 0; i < 1<<n; i++ { res = append(res, i^(i>>1)) // 第 i 个格雷码 = i 与「i 右移一位」的异或 } return res }
$ go build -o bin . && ./bin < cases.jsonl [1] → [0,1] [2] → [0,1,3,2] [3] → [0,1,3,2,6,7,5,4] [4] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8] [5] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16] [6] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,41,43,42,46,47,45,44,36,37,39,38,34,35,33,32]
JavaScript · 解法代码function grayCode(n) { const res = []; for (let i = 0; i < (1 << n); i++) res.push(i ^ (i >> 1)); // 第 i 个格雷码 = i 与「i 右移一位」的异或 return res; }
$ node run.js < cases.jsonl [1] → [0,1] [2] → [0,1,3,2] [3] → [0,1,3,2,6,7,5,4] [4] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8] [5] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16] [6] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,41,43,42,46,47,45,44,36,37,39,38,34,35,33,32]
C++ · 解法代码#include <vector> using namespace std; class Solution { public: vector<int> grayCode(int n) { vector<int> res; for (int i = 0; i < (1 << n); i++) res.push_back(i ^ (i >> 1)); // 第 i 个格雷码 = i 与「i 右移一位」的异或 return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [1] → [0,1] [2] → [0,1,3,2] [3] → [0,1,3,2,6,7,5,4] [4] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8] [5] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16] [6] → [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,51,50,54,55,53,52,60,61,63,62,58,59,57,56,40,41,43,42,46,47,45,44,36,37,39,38,34,35,33,32]
共 10 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 10/10 Java 通过 10/10 Go 通过 10/10 JavaScript 通过 10/10 C++ 通过 10/10
Python 版本另外和镜像反射法对 n 从 1 到 14 做了对拍（n 只有很少的取值，随机取值几乎覆盖了全部）：
随机对拍 14 组（n 取 1 到 14），solve 与 brute 的结果全部一致。
另外四种语言只在上面 10 组固定用例上验证过，其中包含 n = 16（65536 个数）。这道题的耗时完全由输出长度 2^n 决定，所以没有另做规模对比实验。
下面的演示用 n = 3，共 8 个数。逐个 i 算出格雷码：0 → 000，1 → 001，2 → 011，3 → 010，4 → 110，5 → 111，6 → 101，7 → 100，每一步都标出了与上一个数相比不同的那一位。最后首尾 100 和 000 也只差最高的一位。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。