格雷码

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

注意序列的下标我们以 为起点，也就是说 。

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

构造格雷码（变换）

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

手动构造

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

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

交替按照上述策略生成 次，可得到 位的格雷码序列。

镜像构造

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

计算方法

我们观察一下 的二进制和 。可以发现，如果 的二进制第 位为 ，仅当 的二进制第 位为 ，第 位为 或者第 位为 ，第 位为 。于是我们可以当成一个异或的运算，即

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

正确性证明

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

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

于是我们在计算 和 的时侯，后 位都会变成 个 的形式，而第 位是不同的，因为 和 除了后 位，其他位都是相同的。因此第 位要么同时异或 ，要么同时异或 。两种情况，第 位都是不同的。而除了后 位以外的二进制位也是做相同的异或运算，结果是相同的。

证毕。

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

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

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

实际应用

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

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

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

• 格雷码可以用来解决汉诺塔的问题。

  设盘的数量为 。我们从 位全 的格雷码 开始，依次移向下一个格雷码（ 移向 ）。当前格雷码的二进制第 位表示从小到大第 个盘子。

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

  如果 是一个奇数，那么盘子的移动路径为 ，其中 是最开始的柱子， 是最终我们把所有盘子放到的柱子， 是中间的柱子。

  如果 是偶数：

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

习题

• CSP S2 2019 D1T1 Difficulty: easy

• SGU #249 Matrix Difficulty: medium

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