【GESP】C++六级考试大纲知识点梳理, (3) 哈夫曼编码与格雷码

GESP C++六级官方考试大纲中，第3条考点要求掌握两种具体的编码方式及其原理。

（3）理解哈夫曼编码、格雷编码相关原理并能进行简单应用。

六级考点系列：

• 【GESP】C++六级考试大纲知识点梳理, (1) 树的概念与遍历
• 【GESP】C++六级考试大纲知识点梳理, (2) 哈夫曼树、完全二叉树与二叉排序树

本篇将重点介绍格雷码 (Gray Code) 的原理、构造方法及与二进制码的转换，并对哈夫曼编码进行简要回顾与应用总结。

---

一、哈夫曼编码 (Huffman Coding)

1.1 原理回顾

在上一篇 【GESP】C++六级考试大纲知识点梳理, (2) 哈夫曼树、完全二叉树与二叉排序树 中，我们已经详细讲解了哈夫曼树的构造过程以及哈夫曼编码的生成原理。

核心要点：

• 变长编码：高频字符用短编码，低频字符用长编码，以达到压缩数据的目的。
• 前缀编码性质：哈夫曼编码是前缀码，即任一字符的编码都不是另一字符编码的前缀，保证了解码的唯一性。
• 构造依赖：通过构建哈夫曼树，左分支代表 0，右分支代表 1，从根到叶子的路径即为该字符的编码。

1.2 简单应用

在考试中，关于哈夫曼编码的考察通常涉及：

1. 构造树并求WPL：给定一组权值，计算最小带权路径长度（见上一篇示例）。
2. 手动编码：给定字符频率，画出哈夫曼树并写出每个字符的二进制编码。
3. 编码长度计算：计算编码后的总二进制位数，对比定长编码（如ASCII）计算压缩率。

复习建议：请务必熟练掌握哈夫曼树的“贪心合并”过程，这是解题的关键。

---

二、格雷码 (Gray Code)

2.1 什么是格雷码？

格雷码（Gray Code），又称循环二进制单位距离码，是一种特殊的二进制编码方式。它的核心特征是：任意两个相邻的数值（包括首尾），其编码只有一位二进制数不同。

示例（3位二进制码 vs 3位格雷码）：

十进制值	普通二进制 (Binary)	格雷码 (Gray)	差异分析
0	000	000
1	001	001
2	010	011	二进制 001->010 变了2位；格雷码 001->011 变了1位
3	011	010
4	100	110	二进制 011->100 变了3位；格雷码 010->110 变了1位
5	101	111
6	110	101
7	111	100

如何解读格雷码 011？

格雷码不像普通二进制那样，每个位有固定的权重 (如 $2^0, 2^1, 2^2$)。你不能直接把 011 看作 $0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0$ 这样来计算它的十进制值。

正确理解方法：

• 格雷码 011 本身没有直接的十进制含义。
• 它代表的十进制值，需要通过将其转换回普通二进制码才能知道。
• 在我们的对比示例表格中，你可以看到 011 对应的十进制值是 2。这是因为 011 转换回普通二进制是 010，而 010 就是十进制的 2。

2.2 为什么需要格雷码？

格雷码最早由贝尔实验室的弗兰克·格雷（Frank Gray）在1940年代提出，格雷码的主要优势在于它的“一位变化”特性，这使得它在物理世界中进行状态编码时非常有用，尤其是在：

1. 机械传感器 (如旋转编码器)：想象一个转盘上有多个传感器读取位置。如果使用普通二进制，从 011 (十进制3) 到 100 (十进制4) 需要三位同时变化（如 011 -> 010 -> 000 -> 100）。在转盘转动时，这三个传感器不可能完美同步地切换，可能会短暂读到 010、000 等错误值。而格雷码保证相邻状态只变一位，完全避免了这种“瞬时误差”，让读取更稳定可靠。
2. 数字电路和数据传输：在高速变化的信号中，可以减少由于不同信号线延迟不一致而产生的毛刺或错误。

2.3 格雷码的构造与转换

在实际应用和考试中，我们通常面临两种不同的需求：

1. 构造整个序列：需要列出 $n$ 位的所有格雷码（如题目要求“写出3位格雷码序列”）。
2. 快速数值转换：已知一个整数 $x$，求其对应的格雷码（如编程题中 $O(1)$ 时间求值）。

针对这两种需求，有两种对应的方法。

场景一：镜像递归法 (用于构造完整序列)

这是最直观的构造思路。$n$ 位格雷码可以由 $n-1$ 位格雷码推导出来：

1. 将 $n-1$ 位的格雷码序列写下来。
2. 将该序列倒序（镜像）写在下方。
3. 前半部分（原始序列）的开头补 0。
4. 后半部分（镜像序列）的开头补 1。

原理解析

镜像法的巧妙之处在于它如何维持“相邻编码只有一位不同”的核心特性，尤其是在连接新旧序列的“镜像点”处。 假设我们已经有了 $n-1$ 位的格雷码序列 $G_{n-1}$。

1. 构造前半部分：将 $G_{n-1}$ 中每个编码前加 $0$。这一部分内部，相邻编码因为 $G_{n-1}$ 自身的性质，仍然只有一位不同。
2. 构造后半部分：将 $G_{n-1}$ 倒序，然后每个编码前加 $1$。这一部分内部，由于是原序列的倒序，相邻编码也只有一位不同。
3. 连接点：前半部分的最后一个编码是 $0$ + $G_{n-1}$ 的最后一个编码。后半部分的第一个编码是 $1$ + $G_{n-1}$ 的最后一个编码（因为是倒序后的第一个）。这两个编码除了最高位（$0$ vs $1$）不同外，其余 $n-1$ 位完全相同。因此，它们之间也仅有一位不同，保证了整个 $n$ 位格雷码序列的连续性。

演示：从 1 位推导 2 位

1位格雷码：

0
1

镜像：

0
1
--- (镜像线)
1
0

补位：

00
01
--- (镜像线)
11
10

这就是 2 位格雷码：00, 01, 11, 10。

演示：从 2 位推导 3 位

2位格雷码：

00
01
11
10

镜像：

00
01
11
10
--- (镜像线)
10
11
01
00

补位：

000
001
011
010
110
111
101
100

这就是 3 位格雷码：000, 001, 011, 010, 110, 111, 101, 100。

同理可推导更高位的格雷码。

C++ 代码实现 (递归)：

#include <vector>
#include <string>
#include <algorithm> // 用于 std::reverse
#include <iostream>

// 函数：生成 n 位格雷码序列 (使用镜像法)
std::vector<std::string> generateGrayCodeMirror(int n) {
    // 基本情况：0 位格雷码，返回一个包含空字符串的向量
    if (n == 0) {
        return {""};
    }
    // 基本情况：1 位格雷码，直接是 "0", "1"
    if (n == 1) {
        return {"0", "1"};
    }

    // 递归调用：获取 n-1 位格雷码序列
    std::vector<std::string> prevGrayCodes = generateGrayCodeMirror(n - 1);

    std::vector<std::string> currentGrayCodes;

    // 1. 生成前半部分：在每个 n-1 位格雷码前加 '0'
    for (const std::string& code : prevGrayCodes) {
        currentGrayCodes.push_back("0" + code);
    }

    // 2. 生成后半部分：将 n-1 位格雷码序列倒序，然后在每个编码前加 '1'
    // 首先复制并倒序
    std::vector<std::string> reversedPrevGrayCodes = prevGrayCodes;
    std::reverse(reversedPrevGrayCodes.begin(), reversedPrevGrayCodes.end());

    for (const std::string& code : reversedPrevGrayCodes) {
        currentGrayCodes.push_back("1" + code);
    }

    return currentGrayCodes;
}

// 示例用法（可放在 main 函数中测试）
int main() {
    int n_bits = 3; // 想要生成的格雷码位数
    std::vector<std::string> grayCodes = generateGrayCodeMirror(n_bits);

    std::cout << n_bits << " 位格雷码序列 (镜像法):\n";
    for (const std::string& code : grayCodes) {
        std::cout << code << "\n";
    }
    return 0;
}

---

场景二：位运算法 (用于数值快速转换)

在编程中，我们通常使用位运算公式直接进行转换，效率极高。

公式：二进制码 $B$ 转 格雷码 $G$

\[G = B \oplus (B >> 1)\]

即：格雷码 = 二进制码 $\oplus$ (二进制码右移一位)。 (注：$\oplus$ 代表异或运算 XOR)

原理解析与算法图解

1. 深度解密：格雷码到底代表了什么？（逻辑推导）

你可能会觉得二进制 1100 变成格雷码 1010 毫无规律。但其实，格雷码记录的不是数值，而是二进制位的“变化趋势”。

让我们把二进制数看作一排开关。格雷码的生成逻辑非常简单，只有一句话：

格雷码的每一位，记录的都是“对应二进制位”与“它左边那一位”是否不同。

• 不同 $\rightarrow$ 记为 1
• 相同 $\rightarrow$ 记为 0 (注：最高位的左边没有数，我们默认它是 0)

2. 手动推导实例 (以 二进制 1100 为例)

我们不需要任何公式，只用上面的逻辑，就能推导出它的格雷码：

• 看第3位 (最高位)：
  • 二进制是 1。
  • 它左边是 0 (默认)。
  • 不一样 $\rightarrow$ 格雷码记 1。
• 看第2位：
  • 二进制是 1。
  • 它左边(第3位)也是 1。
  • 一样 $\rightarrow$ 格雷码记 0。

• 看第1位：

  • 二进制是 0。
  • 它左边(第2位)是 1。
  • 不一样 $\rightarrow$ 格雷码记 1。

• 看第0位 (最低位)：

  • 二进制是 0。
  • 它左边(第1位)也是 0。
  • 一样 $\rightarrow$ 格雷码记 0。

结果：拼起来就是 1010。

3. 如何把逻辑变成算法？

既然我们的逻辑是：拿“原来的数” 和 “它左边的数” 进行比较。

• 原来的数：就是二进制 $B$。
• 它左边的数：如何让每一位都和左边对齐？ $\rightarrow$ 把整个数字向右移一位！原来的第3位就到了第2位的位置，正好和原来的第2位对齐。这就是 $B » 1$。
• “比较是否不同”：在计算机中，判断两个位是否不同，用的就是 异或运算 ($\oplus$)。

C++ 代码实现：

unsigned long long binaryToGray(unsigned long long n) {
    return n ^ (n >> 1);
}

---

图解演示：

例1：将十进制 6 (二进制 110) 转为格雷码

1. 写出二进制：1 1 0
2. 右移一位： 0 1 1 (最高位补0)
3. 上下异或：

      1 1 0  (二进制 B)
    ^ 0 1 1  (B >> 1)
    -------
      1 0 1  (结果 G)

例2：将十进制 7 (二进制 111) 转为格雷码

      1 1 1  (二进制 B)
    ^ 0 1 1  (B >> 1)
    -------
      1 0 0  (结果 G)

验证特性：

从 6 (110) 变到 7 (111)，二进制码变了 1 位。 对应的格雷码从 101 变到 100，也只变了 1 位（末位）。

2.4 格雷码转回二进制码 (逻辑逆推)

如果已知格雷码 $G$，如何还原为二进制码 $B$？ 利用之前的逻辑：“格雷码记录了与左边邻居的差异”。现在我们要反过来，已知差异，推导原值。

手动还原逻辑： “看格雷，定去留”

我们从最高位开始，一位一位向右推导（因为最高位的左边邻居肯定是 0，是已知的）。

推导规则：

• 格雷码是 0 $\rightarrow$ 表示“与左边相同” $\rightarrow$ 照抄左边刚刚算出来的二进制位。
• 格雷码是 1 $\rightarrow$ 表示“与左边不同” $\rightarrow$ 翻转左边刚刚算出来的二进制位。

图解实例：将格雷码 1010 还原为二进制

• 第3位 (最高位)：
  • 格雷码是 1。
  • 左边邻居是 0 (默认)。
  • 不同 $\rightarrow$ 二进制为 1。
  • (当前二进制序列: 1...)
• 第2位：
  • 格雷码是 0 (表示“和左边一样”)。
  • 左边一位(第3位)算出来是 1。
  • 照抄 $\rightarrow$ 二进制为 1。
  • (当前二进制序列: 11...)
• 第1位：
  • 格雷码是 1 (表示“和左边不一样”)。
  • 左边一位(第2位)算出来是 1。
  • 翻转 $\rightarrow$ 二进制为 0。
  • (当前二进制序列: 110...)
• 第0位：
  • 格雷码是 0 (表示“和左边一样”)。
  • 左边一位(第1位)算出来是 0。
  • 照抄 $\rightarrow$ 二进制为 0。
  • (最终结果: 1100)

代码实现

1. 数学推导 (剥洋葱法)：
   • 根据手动逻辑：当前二进制 $B_i$ = 左边二进制 $B_{i+1}$ $\oplus$ 当前格雷码 $G_i$。 (异或 0 = 保持原值，异或 1 = 翻转，完全符合手动规则)
   • 那 左边二进制 $B_{i+1}$ 是哪来的？它又是 更左边二进制 $B_{i+2}$ $\oplus$ $G_{i+1}$。
   • 一层层剥开，最终你会发现： \(B_i = G_i \oplus G_{i+1} \oplus G_{i+2} \oplus \dots \oplus G_{最高位}\)
   • 结论：某一位的二进制值，实际上等于该位及左边所有位格雷码的“异或和”。
2. 代码示例：

unsigned long long grayToBinary(unsigned long long g) {
    unsigned long long b = g; // 1. 先记录 G 本身 (对应公式中的 G_i)
  
    // 2. 循环右移：
    // 第一次循环：g 右移1位，b ^= g。 相当于加上了 G_{i+1}
    // 第二次循环：g 再右移1位，b ^= g。 相当于加上了 G_{i+2}
    // ... 直到最高位
    while (g >>= 1) {
        b ^= g;
    }
    return b;
}

---

三、总结

知识点	核心原理	关键公式/方法	应用场景
哈夫曼编码	贪心策略，树形结构，前缀码	WPL 最小化构造	数据压缩 (ZIP, JPEG)
格雷码	相邻数值仅一位二进制不同	$G = B \oplus (B » 1)$	旋转编码器、减少硬件误差

学习建议：

1. 对于哈夫曼编码，重点在于画树和计算 WPL。
2. 对于格雷码，重点在于掌握生成规则（镜像法）和代码转换公式（异或法），特别是 $G = n \oplus (n » 1)$ 这一公式在编程题中非常常用。

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号