格雷码

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

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

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

构造格雷码(变换)

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

手动构造

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

  1. 翻转最低位得到下一个格雷码,(例如 );
  2. 把最右边的 的左边的位翻转得到下一个格雷码,(例如 );

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

镜像构造

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

计算方法

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

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

正确性证明

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

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

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

证毕。

通过格雷码构造原数(逆变换)

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

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

实际应用

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

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

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

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

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

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

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

    如果 是偶数:

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

习题

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