格雷编码如何生成？为什么相邻两个数只差一位？

简化版

n 位格雷编码可以用公式 gray(i) = i ^ (i >> 1) 生成，枚举 i 从 0 到 2^n-1。这个公式会让相邻编号映射出的编码只改变一位。

详细版

格雷编码要求序列长度为 2^n，包含所有 n 位二进制数，且相邻两个数二进制表示只有一位不同。最常见生成方式有两种：反射构造法和公式法。公式法最短：第 i 个格雷码是 i ^ (i >> 1)。

时间复杂度 O(2^n)，空间复杂度取决于输出。面试中要能解释右移和异或的作用：每一位格雷码反映原二进制相邻两位是否不同。

完整版教学

一、格雷编码解决什么问题

普通二进制递增时，相邻数字可能改变很多位。例如从 3 到 4：

3 = 011
4 = 100

三个位全变了。格雷编码要求相邻状态只变 1 位，在硬件编码、状态压缩遍历里很有用。

二、公式 `i ^ (i >> 1)` 怎么看

设普通二进制是 b，格雷码 g 的每一位可以理解成相邻二进制位是否发生变化：

g = b ^ (b >> 1)

例如 i=6：

i      = 110
i >> 1 = 011
xor    = 101

所以 6 对应的格雷码是 5。

三、为什么相邻只差一位

从 i 到 i+1，普通二进制会发生进位，低位可能连续翻转。但经过 i ^ (i>>1) 映射后，这些连续翻转会被压缩成格雷码中的单点变化。

i	二进制 i	gray
0	`00`	`00`
1	`01`	`01`
2	`10`	`11`
3	`11`	`10`

记忆钩子：格雷码不是让二进制不进位，而是用异或把进位变化折叠成一位变化。

表里相邻 gray 分别只差 1 位。

四、反射构造法也要理解

另一种直观构造是反射法。n=1 时：

0
1

生成 n=2 时，先原序前面加 0，再反序前面加 1：

反射法可以帮助理解为什么序列首尾也只差一位。

五、代码模板

List<Integer> grayCode(int n) {
    List<Integer> ans = new ArrayList<>();
    int size = 1 << n;
    for (int i = 0; i < size; i++) {
        ans.add(i ^ (i >> 1));
    }
    return ans;
}

输出是整数列表，但每个整数可以用 n 位二进制解释。

六、用 n=3 推演

n=3 时，前几个结果：

i=0: 000 ^ 000 = 000
i=1: 001 ^ 000 = 001
i=2: 010 ^ 001 = 011
i=3: 011 ^ 001 = 010
i=4: 100 ^ 010 = 110

序列是：

000, 001, 011, 010, 110, 111, 101, 100

相邻之间都只有一个 bit 不同。

七、常见误区与追问

误区：直接返回 0 到 2^n-1。 普通二进制相邻数不一定只差一位。
误区：把 >> 1 写成 << 1。 格雷码公式用右移比较相邻高位。
误区：认为输出必须是字符串。 题目通常要求整数，显示时才转二进制。
追问：反射法怎么生成？ 旧序列前加 0，反向旧序列前加 1。
追问：复杂度是多少？ 必须输出 2^n 个数，所以时间 O(2^n)。
追问：格雷码能反解吗？ 可以从高位到低位累积异或还原普通二进制。

八、加强记忆

格雷编码记住一个公式：i ^ (i >> 1)。右移让每一位和它的高一位对齐，异或得到“相邻位是否变化”。如果一时忘了公式，就用反射构造：原序加 0，反序加 1。公式适合写代码，反射适合理解为什么只差一位。

简化版

详细版