随记 – 五月二日 – 初探格雷码

格雷码（Gray code）是一种任意两相邻项有且仅有一位不同的二进制编码。

直观来看，其构造方式如下：假如我们构造出了格雷码$g_{0, 1, \cdots, 2^m-1}$，现在考虑构造$m+1$位格雷码。我们将前$2^m$位复制一遍，然后反转在原序列中的位置，也即$g’_{2^m+i}=g_{2^m-1-i}, i \in [0, 2^m)$；然后在最后$2^m$项格雷码的左侧分别添上$1$。由此有$g_{2^m+i}=g_{2^m-1-i}+2^m$。

实际操作时，可以采用相邻两项的异或值与前缀异或和快速构造。假若有$g_x$与$g_{x-1}$的异或值序列$s_{1, 2, \cdots, 2^m-1}$，那么便有$s_{2^m+i}=s_{i}, i \in [1, 2^m)$，同时有$s_{2^m+1}=g_{2^m+1} \oplus g_{2^m}=2^m$。

例如，前8项格雷码的二进制表示为：$\{\text{0b}000, \text{0b}00{\color{blue}1}, \text{0b}0{\color{blue}1}1, \text{0b}01{\color{blue}0}, \text{0b}{\color{blue}1}10, \text{0b}11{\color{blue}1}, \text{0b}1{\color{blue}0}1, \text{0b}10{\color{blue}0}\}$，相邻两项异或值为$\{1,2,1,4,1,2,1\}$。

下面给出一个构造$n$位格雷码的简单实现。更高效的实现和证明参见OI Wiki。

1
2
3
4
5
6
7
8
9
inl void Gray (int n, int g[]) {
	for (int w = 0; w < n; ++w) {
		g[1<<w] = 1<<(w<<1);
		for (int i = 1; i < 1<<w; ++i)
			g[i + (1<<w)] = g[i];
	}
	for (int i = 1; i < 1<<n; ++i)
		g[i] ^= g[i - 1];
}

格雷码主要有以下两个重要性质：

• 构成一个$0, 1, \cdots, 2^m-1$的全排列。
• 相邻两项恰有$1$位不同。

假若我们需要构造一个$0$到$2^m-1$的全排列，并且考虑相邻两项的异或的算术总和最小，那么最优解一定是格雷码。同时，$2^m$项格雷码的遍历仅需要作$2^m-1$次二进制位的变换；而由于异或具有结合律与相异性，可以利用其构造互不相同的状态的表示，因此容易出现在与异或、最小异或代价等的构造题目中。

题目：

• CSP-S 2019 T1 格雷码：递归构造格雷码。
• AtCoder ARC 138 D – Differ By K-bits / 题解：如果相邻两项的二进制表示恰有$K$位不同呢？（对于$K=1$的特例？
• CF1673F. Anti-Theft Road Planning：相异状态的异或和表示方法，但是二维，且代价最小。
  • Hint: 考虑将一维格雷码的构造推广到二维矩阵上。