GESP6级C++考试语法知识（五、格雷码）

《格雷编码王国大冒险》

——让小学生也能真正理解“格雷编码”！

🌟第一章：灯泡城堡的大危机

1、很久很久以前，在“二进制王国”里，住着一群神奇的小灯泡。

（1）每个灯泡只有两种状态：

• 0 → 熄灭 💡❌

• 1 → 点亮 💡✅

（2）比如：

（3）国王每天都会按顺序切换灯泡。

2、😱问题来了！

（1）有一天，工程师发现：

如果一次切换太多灯泡，机器会出错！

（2）例如：

从：

011

变成：

100

竟然有：

• 第1位变了

• 第2位变了

• 第3位变了

（3）一下变了3个灯泡！

机器“啪”地爆炸了 💥

🌟第二章：格雷骑士登场！

1、这时，一位聪明的骑士出现了。

（1）他叫：

👑 格雷骑士（Gray）

（2）他说：

“每次只改变一个灯泡，不就安全了吗？”

（3）于是，他设计出了：

🌟格雷编码（Gray Code）

（4）规则只有一句：

✅ 相邻两个数，只允许一位不同！

🌟第三章：看看真正的格雷编码

1、普通二进制：

2、你会发现：

001 -> 010

变了2位！

不安全！

3、🌈格雷编码版本

观察一下：

000 -> 001

只变1位 ✅

001 -> 011

只变1位 ✅

011 -> 010

只变1位 ✅

太神奇了！

🌟第四章：为什么叫“格雷编码”？

1、因为它是数学家：

👨‍🔬 Frank Gray

发明的。

2、所以叫：

Gray Code（格雷编码）

🌟第五章：格雷编码到底有什么用？

它可厉害了！

🚪1. 电梯楼层传感器

电梯楼层传感器如果同时变化多位：

可能把3楼看成7楼 😱

格雷编码一次只变1位，更安全。

🎮2. 游戏手柄

旋钮转动时：

使用格雷编码可以避免读错位置。

🚀3. 火箭、机器人

机器特别怕：

“多个开关同时变化”。

格雷编码特别稳定！

🌟第六章：最核心的秘密！

终于来到真正重要的部分了！

1、🎯如何把二进制变成格雷编码？

（1）公式：

✅ Gray = Binary ^ (Binary >> 1)

（2）意思：

格雷码 = 原数字 ^ (原数字右移1位)

2、这里：

^

是位运算：

🌟异或 XOR

🌟第七章：再复习下什么是异或？

异或规则：

口诀：

✅ 一样为0，不一样为1

🌟第八章：真正开始计算！

比如：

🎯求数字 5 的格雷编码

第一步：写二进制

5 的二进制：

101

第二步：右移1位

101 >> 1

变成：

010

第三步：异或

101 010 --- 111

得到：

111

所以：

🎉5 的格雷编码是 111！

🌟第九章：C++程序实现

🌈方法1：求一个数的格雷编码

#include <iostream> using namespace std; int main() { int n; cin >> n; int gray = n ^ (n >> 1); cout << gray; return 0; }

🌟第十章：一步一步看程序

1、🎯输入

5

2、🎯n >> 1

101 -> 010

3、🎯异或

101 010 --- 111

4、🎯输出

7

5、注意：

程序输出的是：

🌟十进制！

6、因为：

111（二进制） = 7（十进制）

🌟第十一章：打印 n 位格雷编码

1、比如：

输出3位格雷编码：

000 001 011 010 110 111 101 100

2、🌟程序

#include <iostream> using namespace std; int main() { int n; cin >> n; //例如输入3 int total = 1 << n; //3位格雷码一共有8个数字 for(int i = 0; i < total; i++) { int gray = i ^ (i >> 1); //使用公式求格雷码（10进制） for(int j = n - 1; j >= 0; j--) { cout << ((gray >> j) & 1); // 按照位次拆回二进制数字 } cout << endl; } return 0; }

🌟第十二章：详细讲解！

🎯1. 什么是

1 << n

？

意思：

🌟2 的 n 次方

例如：

1 << 3

就是：

1000（二进制） = 8

因为：

3位二进制：

000 ~ 111

总共有：

8 个状态！

🎯2. 为什么：

(gray >> j) & 1

能取出某一位？

例如：

gray = 111

j=2

111 >> 2 = 001

再：

001 & 1 = 1

说明第2位是1。

🌟第十三章：神奇规律！

观察：

你会发现：

🌟每次只变1位！

这就是格雷编码最大的特点！

🌟第十四章：小游戏理解

1、🎮灯泡挑战赛

有3个灯泡：

000

每次：

只能改一个灯泡！

你能不能走遍所有状态？

答案就是：

🌟格雷编码顺序！

2、🌟第十五章：常见应用

🌈1. 状态压缩

很多算法：

会用二进制表示状态。

格雷编码可以：

让状态变化更平滑。

🌈2. 枚举所有状态

比如：

• 开关问题

• 迷宫问题

• 电路问题

🌈3. 汉诺塔

汉诺塔移动规律，

其实和格雷编码非常像！

因为：

每次也只移动一个盘子！

🌟第十六章：记忆口诀！

🌈格雷编码口诀

相邻只变一位码， 机器读取不害怕。 原数右移再异或， Gray编码就是它！

🌟第十七章：小挑战！

🎯挑战1

求：

6

的格雷编码。

🎯挑战2

输出3位格雷编码。

🎯挑战3

为什么：

011 -> 010

只变化1位？

看看是哪一位变了！

🌟最终总结

1、🎯什么是格雷编码？

一种：

🌟相邻状态只改变1位的编码！

2、🎯核心公式

gray = n ^ (n >> 1)

3、🎯核心优点

✅ 不容易出错
✅ 更稳定
✅ 机器特别喜欢

4、🎯核心思想

🌟“一次只改一点点！”

这其实也是很多算法的重要思想！