格雷编码：相邻数字只改变一位的“安全密码”

格雷编码：让数字变化只变一位的“安全密码”——从灯泡游戏到递归实现

你有没有玩过这样的游戏：面前有一排灯泡，每次只能改变其中一个灯泡的亮灭，你想把所有可能的亮灭组合都走一遍，而且希望每次只变化一个灯泡？如果你按普通的二进制数顺序（从0到7）去操作，会遇到一个麻烦：比如从 0111（7）变成 1000（8），一下子要改变4个灯泡——手一抖，中间可能闪出别的错误组合。怎样才能让相邻两个状态只变化一位呢？科学家弗兰克·格雷想到了一个巧妙的编码方式，这就是格雷编码（Gray Code）。

格雷编码是一种特殊的二进制数表示法，它保证任意两个相邻的数值之间，只有一位二进制位不同。就像翻书时每次只翻一页，不容易出错。这种编码在数字电路、通信、角度传感器（比如旋转编码器）中非常有用——因为电子设备在多位同时变化时容易产生毛刺，而格雷编码只变一位，天然避免了这种风险。

生活中的例子：电梯按钮与密码锁

想象一个电梯，它的楼层指示器用3个LED灯表示（每个灯亮表示“1”，灭表示“0”）。如果按普通二进制，从“011”（楼层3）到“100”（楼层4）时，三个灯都要变：灭亮亮 → 亮灭灭。如果某个灯反应慢了一点，乘客可能会先看到“111”或“000”之类乱七八糟的楼层数，吓一大跳。但如果用格雷编码，相邻楼层只变一个灯，比如“010”（楼层2）→“110”（楼层3）→“111”（楼层4）→“101”（楼层5）……这样就平稳多了。很多旋转角度传感器（比如游戏手柄的摇杆）内部用的就是格雷编码，确保旋转时不会跳变。

格雷编码的构造方法：递归镜像法

假设我们已经有了 n-1 位的格雷码，如何得到 n 位的格雷码？有一个经典的“镜像法”，步骤很简单：

先写出 n-1 位格雷码，按顺序列出来。
上下对称复制：把这个序列倒序写在下面。
前半部分前面加“0”，后半部分前面加“1”。

例如，1位格雷码：0, 1。

要生成2位：先原序加0得 00, 01；再倒序加1得 11, 10。合并后：00, 01, 11, 10。验证：00→01只变末位，01→11只变首位，11→10只变末位，完美。
要生成3位：复制2位序列：00,01,11,10；倒序是10,11,01,00；前面一半加0：000,001,011,010；后面一半加1：110,111,101,100。最终得到8个编码，相邻只差一位。

你可能会问：为什么镜像法能保证相邻只变一位？因为原序列本身已经满足相邻只差一位，而倒序后相邻的两个码（最后一个原序和第一个倒序）在原序列中就是首尾相连，但它们的区别是？实际上镜像法在中间衔接处（原序最后一个和倒序第一个）用对称性保证了只差一位——因为原序的最后一个和倒序的第一个是相同的码反转后的结果，在加0和加1后，它们只差最高位（0变1），其他位相同。完美！

递归生成格雷码的C++程序（完整示例）

下面是一个用递归思想实现上述过程的C++程序。它从1位开始，逐层构造，最终输出n位格雷码。代码中每行变量定义都加了中文注释，方便你理解。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 递归生成n位格雷码，返回字符串向量
vector<string> generateGray(int n) {
    // 基础情况：1位格雷码只有"0"和"1"
    if (n == 1) {
        return {"0", "1"};
    }
    // 先递归得到 n-1 位的格雷码
    vector<string> prev = generateGray(n - 1);
    vector<string> result;  // 保存最终结果
    // 前半部分：在原来的每个码前面加 '0'，顺序保持不变
    for (const string& code : prev) {
        result.push_back("0" + code);
    }
    // 后半部分：在原来的每个码前面加 '1'，但要倒序添加（镜像对称）
    for (int i = prev.size() - 1; i >= 0; --i) {
        result.push_back("1" + prev[i]);
    }
    return result;
}

int main() {
    int n;  // 用户输入的格雷码位数
    cout << "请输入格雷码位数（比如3）: ";
    cin >> n;
    // 生成n位格雷码
    vector<string> grayCodes = generateGray(n);
    // 输出结果
    cout << n << "位格雷码有" << grayCodes.size() << "个:" << endl;
    for (const string& code : grayCodes) {
        cout << code << endl;
    }
    return 0;
}

运行这个程序，输入 3，你会看到输出：

相邻两个数比较一下：000→001只变最后一位，001→011只变中间一位，011→010只变最后一位……确实每次只改变一位。总共8个编码，完美覆盖了3位二进制的所有可能状态（2^3=8）。

另一种快速生成方法：二进制数异或变换

除了递归镜像法，格雷编码还可以直接通过普通二进制数算出来：对于二进制数 i，对应的格雷码 g 可以通过 g = i ^ (i >> 1) 得到（^ 是异或运算）。例如，二进制 3 是 011，右移一位得 001，异或得 010，正好是格雷码列表中的第3个（从0开始）。不过递归镜像法更容易理解“为什么相邻只变一位”，而异或法更便于计算机快速计算。你可以作为拓展了解，但在初学阶段，先掌握递归的思路更重要。

新手容易踩的坑

忘记基础情况：递归一定要有终止条件。if (n == 1) 不能写成 if (n == 0)，因为0位格雷码理论上只有一个空串，但通常我们从1位开始。如果你传入n=0，程序会一直递归下去导致栈溢出。
倒序写错方向：后半部分必须倒序添加，否则你得到的就不是格雷码。有人可能会写成正序列加“1”，那样相邻编码可能会变多位。比如2位格雷码如果正序加1得到00,01,10,11，相邻00→01只变一位，但01→10变了两位！所以必须镜像。
误以为格雷码只有一种：其实格雷码有多种变体（比如反射格雷码、旋转格雷码等），但这里介绍的是最常用的反射格雷码（Binary Reflected Gray Code）。只要记住“镜像法”得到的这种。
输出顺序与二进制顺序不同：格雷码的数值不是从小到大排列的，比如3位格雷码中 100 是最后一个，对应十进制4，但它的前一个是 101（十进制5）。所以不能直接用普通二进制排序来理解。

小练习：自己试试

把上面的程序复制到你的C++开发环境里，试试输入不同的n（比如2、4、5）。观察输出个数是不是2^n个。再验证一下相邻两个编码是不是只差一位（可以用眼睛或写个小循环检查）。如果你觉得递归不好理解，可以手工画出 n=1→2→3 的镜像过程，一步步跟着走一遍，很快就能掌握。

格雷编码就像一串“安全密码”，让数字变化变得平滑、可靠。下次你看到电梯楼层指示器、游戏手柄转盘，甚至一些数字电路芯片，都可以想想：这里面是不是藏着每次只变一位的格雷码呢？