格雷码 知识点讲解

概念

在信息学竞赛中，有些题目会给出一个巨大的数字，让你判断它是不是某个数的“格雷码”，或者让你生成第 $k$ 个格雷码。如果你直接去写一个循环，从 0 开始一个个生成格雷码，直到第 $k$ 个，当 $k$ 是 $10^{18}$ 这种级别时，你的程序会跑上天，直接超时（TLE）。这时候，你需要的就是格雷码。

格雷码（Gray code）是一种特殊的二进制编码方式。它最神奇的地方在于：任意两个相邻的码字之间，只有一位二进制不同。

为了理解为什么要设计这么奇怪的编码，我们先看一个普通二进制数变化的场景。假设我们有一个三位二进制计数器，从 3（二进制 011）变到 4（二进制 100）。

在现实世界中，比如旋转编码器或 ADC（模数转换器），这三位可能代表三个物理开关。当数值从 3 跳变到 4 时，这三个开关会同时动作。由于机械或电子延迟，它们几乎不可能在同一毫秒内完成切换。哪怕其中有一个开关慢了 0.1 微秒，读出来的结果就会变成 111（即 7）或者 000（即 0）。这就是所谓的“多位数同时跳变不可靠”，会导致巨大的读数误差。

格雷码就是为了解决这个“多位数同时跳变”而设计的。它强制规定：每次只变一位。这样，无论硬件有多慢，只要保证这一位变对了，其他位没变，读出来的数就一定是正确的相邻数。

大白话翻译：格雷码不是另一种数，而是同一种整数的“防抖动写法”。十进制 0,1,2,3… 依旧是那些数，只是把它们编码成相邻的只差一位的形式，让硬件读起来更安全。

触发清单（看到这些信号第一时间想到本知识点）

定义

① 定义（结论）

• 相邻性：$n$ 位格雷码是 $0 \dots 2^n-1$ 这 $2^n$ 个数的一个排列，排列后相邻两个码只有一位不同。
• 循环性：把序列首尾相接，最后一个和第一个也只差一位，叫循环格雷码。

② 核心公式（重点，必须会推导）

设一个整数的普通二进制为 B，它对应的格雷码为 G，则：

G = B ^ (B >> 1)

也就是「格雷码 = 二进制数 异或 它自己右移一位」。逐位写出来（设 B 的各位为 b₀b₁b₂…，b₀ 是最低位）：

gᵢ = bᵢ ⊕ bᵢ₊₁ （i ≥ 0，最高位 bₙ 视作 0）

特别地，最高位 g₀ = b₀（因为 B>>1 后最高位补 0，异或 0 不变）；其余位是「本位 ⊕ 高位」。

用 n=3 走查验证（列出 0..7 的 B 与 G）：

首尾 000 与 100 也只差最高位 1 位 ✓（循环性成立）。可见公式正确。

③ 逆变换（由格雷码还原二进制）

利用异或的性质 x ^ x = 0、(a^b)^b = a（连续异或两次还原），可以反推 B。由 gᵢ = bᵢ ⊕ bᵢ₊₁，从高位往低位依次解：

bₙ₋₁ = gₙ₋₁
bᵢ = gᵢ ⊕ bᵢ₊₁ （i 从 n-2 递减到 0）

等价于一个紧凑写法：

B = G ^ (G >> 1) ^ (G >> 2) ^ … ^ (G >> n)

推导思路（为什么 B = G ^ (G>>1) 不成立，要一直异或下去）：因为 G = B ^ (B>>1)，G ^ (G>>1) 会把 bᵢ₊₁ 贡献两次抵消掉一部分但不彻底；只有把所有 G>>k 异或，才能把每一位的高位依赖层层消去，最终还原 B。竞赛中常直接给公式 B = G ^ (G>>1) ^ (G>>2) ^ ... ^ (G>>(n-1))，或用循环 b[i] = g[i] ^ b[i+1] 从高位递推。

④ 递推构造（反射法）

$n$ 位格雷码可以由 $n-1$ 位格雷码构造：

1. 先写出所有 (n−1) 位格雷码，作为「上半部分」，前面补 0。

2. 把 (n−1) 位格雷码上下颠倒（反射）作为「下半部分」，前面补 1。

3. 拼起来就是 $n$ 位格雷码。

手算 n=1→2→3：

• n=1：0, 1
• n=2：上半 00, 01；下半反射 01→10, 00→11 ⇒ 00, 01, 11, 10
• n=3：上半 000,001,011,010；下半反射 010→110,011→111,001→101,000→100 ⇒ 000,001,011,010,110,111,101,100（与第②点表一致 ✓）

这个「先 0 前缀、再反射加 1 前缀」的过程，正好对应公式 G = B ^ (B>>1) 的结构，两者是同一件事的两种表达。

⑤ 性质与用途

• ADC / 编码器：位置传感器读数时每次只变一位，避免多位的同步跳变误差（开头说的动机）。
• 卡诺图（Karnaugh Map）：画卡诺图时按格雷码顺序排列行/列，相邻格子只差一个变量，便于圈出最简与或式。
• CSP 真题：CSP-S 2019 考过格雷码（见下），属于「位运算 + 递推」经典题。

例题

例 1（编码）：求十进制 5 的 3 位格雷码

题目描述

给定一个十进制整数 $x$ 和位数 $n$，求 $x$ 对应的 $n$ 位格雷码（不足 $n$ 位前面补 0）。

审题分析

• 输入：$n$（位数），$x$（十进制数）。
• 需求：输出 $n$ 位二进制串，表示 $x$ 的格雷码。
• 为什么能用本知识点：题目明确要求“格雷码”，且 $n$ 较小（如 3 位），直接套用公式 $G = B \oplus (B \gg 1)$ 即可。
• 如果不用本知识点：若误以为格雷码是 $x+1$ 或 $x-1$ 的编码，会得到完全错误的序列，无法通过测试。

解题思路

1. 将 $x$ 转为二进制（或直接操作 $x$ 的位）。

2. 计算 $g = x \oplus (x \gg 1)$。

3. 按 $n$ 位宽度从高位到低位输出 $g$ 的二进制位。

C++ 完整参考代码

#include <iostream>
using namespace std;

int main() {
 int n, x;
 if (!(cin >> n >> x)) return 0;
 // 核心公式：格雷码 = 二进制数 异或 它自己右移一位
 int g = x ^ (x >> 1);
 // 按 n 位宽度输出（高位补 0）
 for (int i = n - 1; i >= 0; i--) cout << ((g >> i) & 1);
 cout << '\n';
 return 0;
}

代码解读（含真实运行输出）

• x ^ (x >> 1) 直接得到格雷码的整数值。
• 循环从 n-1 到 0，每次取第 i 位 (g >> i) & 1，保证输出固定 $n$ 位。
• 输入 3 5 时，$x=5$（二进制 101），$x>>1=2$（010），$g=101\oplus010=111$（十进制 7）。
• 输出为 111。

验证

查前文表格，十进制 5 对应的 3 位格雷码确实是 111，与代码输出一致。

例 2（解码）：由格雷码还原二进制

题目描述

给定一个 $n$ 位格雷码（以二进制串形式给出），求其对应的十进制整数。

审题分析

• 输入：$n$，以及 $n$ 个字符组成的二进制串 $G$。
• 需求：输出对应的十进制数 $B$。
• 为什么能用本知识点：题目是格雷码的逆运算，必须使用逆变换公式。
• 如果不用本知识点：若直接按二进制串解析为十进制，会得到错误答案（例如 110 会被当成 6，而实际对应 4）。

解题思路

1. 将二进制串转为整数 $g$。

2. 使用递推式从高位到低位还原：

$b_{n-1} = g_{n-1}$，

$b_i = g_i \oplus b_{i+1}$（$i$ 从 $n-2$ 递减到 $0$）。

3. 输出 $b$ 的十进制值。

C++ 完整参考代码

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

int main() {
 int n;
 string s;
 if (!(cin >> n >> s)) return 0;
 // 将格雷码字符串转为整数
 int g = 0;
 for (int i = 0; i < n; i++) {
 if (s[i] == '1') g |= (1 << (n - 1 - i));
 }
 // 逆变换递推：从高位到低位
 int b = 0;
 for (int i = n - 1; i >= 0; i--) {
 // 最高位直接等于格雷码最高位
 if (i == n - 1) b = (g >> i) & 1;
 else b = ((g >> i) & 1) ^ b;
 }
 cout << b << '\n';
 return 0;
}

代码解读（含真实运行输出）

• 先将字符串 s 按位解析为整数 g。
• 循环中 b 初始为 0，每次更新为当前格雷码位与上一位 b 的异或。
• 输入 3 110 时，$g=6$（二进制 110）。

- $i=2$: $b = (6>>2)&1 = 1$

- $i=1$: $b = ((6>>1)&1) \oplus 1 = 1 \oplus 1 = 0$

- $i=0$: $b = ((6>>0)&1) \oplus 0 = 0 \oplus 0 = 0$

• 输出 100 即十进制 4。

验证

查前文表格，格雷码 110 对应的十进制数确实是 4，与代码输出一致。

例题复盘总结

本模块只有一道真题风格例题（CSP-S 2019 格雷码），其核心就是公式法 $G = k \oplus (k \gg 1)$。

• 共性特征：所有格雷码相关题目都围绕“相邻性”和“循环性”展开，要么要求生成第 $k$ 个，要么要求解码。
• 各自技巧：生成用公式 $O(1)$；解码用递推异或；构造整张表用反射法。
• 审题模板：看到“格雷码”立刻想到公式；看到“还原”立刻想到递推；看到“生成第 $k$ 个”立刻想到 $k \oplus (k \gg 1)$。
• 错误清单：除了前文已列出的常见错误（如记反移位方向、逆变换不完整等），本题特有的错误是忘记按 $n$ 位宽度补前导 0，导致输出位数不足被判错。

写法总表

与触发清单/速查表的分工：触发清单告诉你“什么时候用”，速查表告诉你“怎么用”，写法总表则按技法粒度由细到粗归纳具体实现。

常见错误

1. 把格雷码当成「二进制减一 / 加一」：错。格雷码不是数值运算，是编码重排；3 的格雷码不是 2 的格雷码加 1。必须用 B ^ (B>>1) 或反射法。

2. 记反公式写成 G = B ^ (B<<1)：错，是右移 B>>1，不是左移。左移会把位关系搞反。

3. 逆变换只写 B = G ^ (G>>1) 就完事：错，这只还原了一步，高位依赖没消干净。正确要一路异或 G>>1, G>>2, … 或用 b[i]=g[i]^b[i+1] 递推。

4. 输出不补到 n 位：题目要求 $n$ 位宽时，高位要补 0（如 $n=3$、$G=1$ 应输出 001 而非 1）。

5. 误以为相邻格雷码「数值」相邻：错，相邻指的是「编码只差一位」，对应的十进制数往往不连续（如 010=3 与 110=4 之间跳了）。

自测

1. 格雷码的两个核心性质（相邻性、循环性）分别是什么？它解决了什么实际问题？

2. 默写公式 G = B ^ (B>>1)，并用 $n=3$ 验证十进制 2、3、6 的格雷码。

3. 由格雷码 G=101 反推原二进制 $B$（写出递推步骤与结果）。

4. 用反射法手推 $n=2$ 与 $n=3$ 的格雷码序列，并核对它们相邻只差一位。

5. 判断题：格雷码就是把二进制数加一后再编码。（ ）并说明理由。

6. 为什么逆变换不能只写 B = G ^ (G>>1)？正确的递推式是什么？

7. （CSP-S 2019 风格）给定 $n$ 与 $k$，输出第 $k$ 个 $n$ 位格雷码的二进制串——写出核心代码行。

举一反三 · 审题流水线

• 第一步：抓关键词。看到“格雷码”“相邻只有一位不同”“循环”“编码器”“ADC”立刻拉响警报，这是本知识点的专属信号。
• 第二步：定需求。题目是生成第 $k$ 个？解码？构造序列？生成用公式，解码用递推，构造用反射。
• 第三步：验边界。$k$ 可能很大（64 位），必须用 long long；输出宽度 $n$ 要补前导 0。
• 第四步：防陷阱。别把格雷码当成数值加减，别记反移位方向，别以为逆变换一次异或就够了。
• 第五步：写代码。公式法一行搞定，递推法循环异或，反射法数组拼接。

练手题

题目一：格雷码解码器

输入一个整数 $G$（保证是某 $n$ 位格雷码），输出对应的十进制数 $B$。

提示：直接读入 $G$，用递推式 $b_{n-1}=g_{n-1}$，$b_i=g_i\oplus b_{i+1}$ 即可。注意 $n$ 未知，但 $G$ 的二进制位数就是 $n$，可通过 __builtin_clz 或手动扫描得到。

题目二：反射构造验证

给定 $n$，按反射法生成 $n$ 位格雷码序列，然后检查序列中任意相邻两项（包括首尾）的二进制差异是否恰好为 1。

提示：生成序列用 vector<string> 或 vector<int>，比较时用异或后统计 1 的个数。