给我简单讲解：格雷码

格雷码（Gray Code）是初赛（CSP-J/S 及海中自招）中高频必考的编码知识点（CSP-S 2019 Day 1 第 1 题就直接考了格雷码生成）。

用最通俗易懂的方式，掌握以下 3 个核心 即可完全吃透：

一、什么是格雷码？为什么需要它？

• 普通二进制的缺点：
  从 $3$ 变到 $4$：011 $\to$ 100，3 个 bit 同时翻转。在真实的硬件传感器或芯片电路中，多位同时跳变极易因为微小的纳秒级延迟产生毛刺干扰和读数错误。
• 格雷码的本质：
  任意相邻的两个数，二进制表示中只有 1 位（bit）不同。
  （首尾相接也是只差 1 位，因此也是一种循环码）。

3 位格雷码与普通二进制对照：

二、考点 1：二进制转格雷码（秒杀公式）

如果你已知十进制或二进制数 $B$，求对应的格雷码 $G$：

即：原数异或上原数右移 1 位。

手算口诀：

1. 最高位不变：$g_n = b_n$；
2. 其余每位等于原码该位与高一位“异或”：$g_i = b_{i+1} \oplus b_i$。

• 实战演练：把二进制 1011 转换为格雷码

    B      =  1  0  1  1
    B >> 1 =  0  1  0  1   (右移补0)
  ----------------------- (按位异或)
    G      =  1  1  1  0
  

  结果就是 1110，考场上 3 秒得出！

三、考点 2：格雷码还原回二进制（解码）

已知格雷码 $G$，求它代表的原二进制 $B$。

手算口诀（从左往右前缀异或累积）：

1. 最高位直接抄下来：$b_n = g_n$；
2. 往后每一位，用“刚算出的上一位二进制”与“当前格雷码位”做异或：$$b_i = b_{i+1} \oplus g_i$$

• 实战演练：把格雷码 1110 还原为普通二进制
  • 最高位：$b_3 = g_3 = \mathbf{1}$
  • 次高位：$b_2 = b_3 \oplus g_2 = 1 \oplus 1 = \mathbf{0}$
  • 第三位：$b_1 = b_2 \oplus g_1 = 0 \oplus 1 = \mathbf{1}$
  • 最低位：$b_0 = b_1 \oplus g_0 = 1 \oplus 0 = \mathbf{1}$
  • 拼起来得到二进制 1011（还原正确）。

四、考点 3：镜像构造法（递归生成）

$n$ 位格雷码可以由 $n-1$ 位格雷码**“镜像翻转”**推出来：

1. 1 位格雷码：0, 1
2. 2 位格雷码：
   • 前半部分：在 1 位码前加 0 $\to$ 00, 01
   • 后半部分：把 1 位码倒序并在前面加 1 $\to$ 11, 10
3. 3 位格雷码：
   • 前半部分（加0）：000, 001, 011, 010
   • 后半部分（倒序加1）：110, 111, 101, 100

考题常见问法（如“求 $n$ 位格雷码中排名第 $k$ 个的编码”）：

• 若 $k < 2^{n-1}$，首位填 0，继续在 $n-1$ 位中找第 $k$ 个；
• 若 $k \ge 2^{n-1}$，首位填 1，接下来在 $n-1$ 位中找第 $(2^n - 1 - k)$ 个（倒序找）。

考场速记卡

// 1. 二进制转格雷码 (一行搞定)
unsigned int binaryToGray(unsigned int n) {
    return n ^ (n >> 1);
}

// 2. 格雷码转二进制 (从高到低异或累加)
unsigned int grayToBinary(unsigned int g) {
    unsigned int b = 0;
    for (; g > 0; g >>= 1) {
        b ^= g;
    }
    return b;
}