跳转至

# 格雷码

格雷码是一个二进制数字系统，其中两个相邻数的二进制位只有一位不同．举个例子，3 3 位二进制数的格雷码序列为

0 0 0,0 0 1,0 1 1,0 1 0,1 1 0,1 1 1,1 0 1,1 0 0 000,001,011,010,110,111,101,100

注意序列的下标我们以 0 0 为起点，也就是说 𝐺(0) =0 0 0,𝐺(4) =1 1 0 G(0)=000,G(4)=110．

格雷码由贝尔实验室的 Frank Gray 于 1940 年代提出，并于 1953 年获得专利．

## 构造格雷码（变换）

格雷码的构造方法很多．我们首先介绍手动构造方法，然后会给出构造的代码以及正确性证明．

### 手动构造

𝑘 k 位的格雷码可以通过以下方法构造．我们从全 0 0 格雷码开始，按照下面策略：

1. 翻转最低位得到下一个格雷码，（例如 0 0 0 →0 0 1 000→001）；
2. 把最右边的 1 1 的左边的位翻转得到下一个格雷码，（例如 0 0 1 →0 1 1 001→011）；

交替按照上述策略生成 2 𝑘−1 2 k−1 次，可得到 𝑘 k 位的格雷码序列．

### 镜像构造

𝑘 k 位的格雷码可以从 𝑘 −1 k−1 位的格雷码以上下镜射后加上新位的方式快速得到，如下图：

𝑘=1 0 1→0 1 1 0→𝑘=2 0 0 0 1 1 1 1 0→0 0 0 1 1 1 1 0 1 0 1 1 0 1 0 0→𝑘=3 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0 k=1 0 1→0 1 1 0→k=2 0 0 0 1 1 1 1 0→0 0 0 1 1 1 1 0 1 0 1 1 0 1 0 0→k=3 0 00 0 01 0 11 0 10 1 10 1 11 1 01 1 00

### 计算方法

我们观察一下 𝑛 n 的二进制和 𝐺(𝑛)G(n)．可以发现，如果 𝐺(𝑛)G(n) 的二进制第 𝑖 i 位为 1 1，仅当 𝑛 n 的二进制第 𝑖 i 位为 1 1，第 𝑖 +1 i+1 位为 0 0 或者第 𝑖 i 位为 0 0，第 𝑖 +1 i+1 位为 1 1．于是我们可以当成一个异或的运算，即

𝐺(𝑛)=𝑛⊕⌊𝑛 2⌋G(n)=n⊕⌊n 2⌋

    1
    int g(int n) { return n ^ (n >> 1); }

### 正确性证明

接下来我们证明一下，按照上述公式生成的格雷码序列，相邻两个格雷码的二进制位有且仅有一位不同．

我们考虑 𝑛 n 和 𝑛 +1 n+1 的区别．把 𝑛 n 加 1 1，相当于把 𝑛 n 的二进制下末位的连续的 1 1 全部变成取反，然后把最低位的 0 0 变成 1 1．我们这样表示 𝑛 n 和 𝑛 +1 n+1 的二进制位：

(𝑛)2=⋯0 1 1⋯1 1⏟𝑘 个(𝑛+1)2=⋯1 0 0⋯0 0⏟𝑘 个(n)2=⋯0 11⋯11⏟k 个(n+1)2=⋯1 00⋯00⏟k 个

于是我们在计算 𝑔(𝑛)g(n) 和 𝑔(𝑛 +1)g(n+1) 的时侯，后 𝑘 k 位都会变成 1 0 0⋯0 0⏟𝑘 个 100⋯00⏟k 个 的形式，而第 𝑘 +1 k+1 位是不同的，因为 𝑛 n 和 𝑛 +1 n+1 除了后 𝑘 +1 k+1 位，其他位都是相同的．因此第 𝑘 +1 k+1 位要么同时异或 1 1，要么同时异或 0 0．两种情况，第 𝑘 +1 k+1 位都是不同的．而除了后 𝑘 +1 k+1 位以外的二进制位也是做相同的异或运算，结果是相同的．

证毕．

## 通过格雷码构造原数（逆变换）

接下来我们考虑格雷码的逆变换，即给你一个格雷码 𝑔 g，要求你找到原数 𝑛 n．我们考虑从二进制最高位遍历到最低位（最低位下标为 1 1，即个位；最高位下标为 𝑘 k）．则 𝑛 n 的二进制第 𝑖 i 位与 𝑔 g 的二进制第 𝑖 i 位 𝑔 𝑖 g i 的关系如下：

𝑛 𝑘=𝑔 𝑘 𝑛 𝑘−1=𝑔 𝑘−1⊕𝑛 𝑘=𝑔 𝑘⊕𝑔 𝑘−1 𝑛 𝑘−2=𝑔 𝑘−2⊕𝑛 𝑘−1=𝑔 𝑘⊕𝑔 𝑘−1⊕𝑔 𝑘−2 𝑛 𝑘−3=𝑔 𝑘−3⊕𝑛 𝑘−2=𝑔 𝑘⊕𝑔 𝑘−1⊕𝑔 𝑘−2⊕𝑔 𝑘−3⋮𝑛 𝑘−𝑖=𝑖⨁𝑗=0 𝑔 𝑘−𝑗 n k=g k n k−1=g k−1⊕n k=g k⊕g k−1 n k−2=g k−2⊕n k−1=g k⊕g k−1⊕g k−2 n k−3=g k−3⊕n k−2=g k⊕g k−1⊕g k−2⊕g k−3⋮n k−i=⨁j=0 i g k−j

    1
    2
    3
    4
    5
    int rev_g(int g) {
      int n = 0;
      for (; g; g >>= 1) n ^= g;
      return n;
    }

## 实际应用

格雷码有一些十分有用的应用，有些应用让人意想不到：

- 𝑘 k 位二进制数的格雷码序列可以当作 𝑘 k 维空间中的一个超立方体（二维里的正方形，一维里的单位向量）顶点的哈密尔顿回路，其中格雷码的每一位代表一个维度的坐标．

- 格雷码被用于最小化数字模拟转换器（比如传感器）的信号传输中出现的错误，因为它每次只改变一个位．

- 格雷码可以用来解决汉诺塔的问题．

  设盘的数量为 𝑛 n．我们从 𝑛 n 位全 0 0 的格雷码 𝐺(0)G(0) 开始，依次移向下一个格雷码（𝐺(𝑖)G(i) 移向 𝐺(𝑖 +1)G(i+1)）．当前格雷码的二进制第 𝑖 i 位表示从小到大第 𝑖 i 个盘子．

  由于每一次只有一个二进制位会改变，因此当第 𝑖 i 位改变时，我们移动第 𝑖 i 个盘子．在移动盘子的过程中，除了最小的盘子，其他任意一个盘子在移动的时侯，只能有一个放置选择．在移动第一个盘子的时侯，我们总是有两个放置选择．于是我们的策略如下：

  如果 𝑛 n 是一个奇数，那么盘子的移动路径为 𝑓 →𝑡 →𝑟 →𝑓 →𝑡 →𝑟 →⋯f→t→r→f→t→r→⋯，其中 𝑓 f 是最开始的柱子，𝑡 t 是最终我们把所有盘子放到的柱子，𝑟 r 是中间的柱子．

  如果 𝑛 n 是偶数：𝑓 →𝑟 →𝑡 →𝑓 →𝑟 →𝑡 →⋯f→r→t→f→r→t→⋯

- 格雷码也在遗传算法理论中得到应用．

## 习题

- CSP S2 2019 D1T1 Difficulty: easy

- SGU #249 Matrix Difficulty: medium

> 本页面部分内容译自博文 Код Грея 与其英文翻译版 Gray code．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．

> 本页面最近更新：2026/1/30 14:50:40，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, frank-xjh, Ir1d, ouuan, StudyingFather, CCXXXI, Early0v0, Enter-tainer, Henry-ZHR, mingyEx, sshwy, Yanjun-Zhao, danni, danni, IgnotaYun, infiWang
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用