# 格雷码问题

> source: 文章/gray-code/index.md

本篇的灵感来源是之前的汉诺塔问题

⬆️ 因此我需要添加一个将文章链接起来的功能

参考 leetcode [89.格雷编码](https://leetcode.cn/problems/gray-code/description/), [1238.循环码排列](https://leetcode.cn/problems/circular-permutation-in-binary-representation/)

## 定义

格雷码的定义方式为每个邻近数字都只相差一个位元, 可以使装置做数字步进时只需要动最少的位元数, 以此提高稳定性

根据中文维基百科，格雷码是循环二进制单位距离码，是任意两个相邻数的代码只有一位二进制数不同的编码，最初用在发送信息时防止出错上，比如从 `3 -> 4` 的时候，需要从 `011 -> 100`，发现三位数字都发生了变换，这就很容易出错，因此格雷码的出现使得每次步进都只有一位发生变化，增强了稳定性 `010 -> 110`

```text
0  　　 000    000
1  　　 001    001
2   　　 011    010
3   　　 010    011
4   　　 110    100
5   　　 111    101
6   　　 101    110
7   　　 100    111
```

对于格雷码 $G(n)$，它一定是 $0, 1, 2, \dots, 2^n - 1$ 在二进制中的某个排列，因为我们需要让这些数字全部都在编码中能够有一一对应, 只不过现在相比与一般的由小到大的排列，顺序发生了变化，实际上它们确实遵循着某种排列顺序，只不过规律并不显而易见

又因为这个排列中相邻的元素只能相差一个位元，因此开头和结尾也是相差一个的，或者说你可以说这个编码会形成一个环，并没有开头或结尾，你可以从任何一个地方开始

## 位运算：$G(n) = B(n+1) \ \mathrm{XOR}\ B(n)$

对于一个整数 $n$，其格雷码 $G(n)$ 的定义：

$$
G(n) = n \ \mathrm{XOR}\ (n >> 1)
$$

按位展开：$B_n = b_{k-1}b_{k-2}\cdots b_1b_0$，$G_n = g_{k-1}g_{k-2}\cdots g_1g_0$，则

$$
g_i = b_{i+1}\ \mathrm{XOR}\ b_i
$$

最高位保持不变：$g_{k-1} = b_{k-1}$。假如我们有一个 4 位二进制数 `b3 b2 b1 b0`，其格雷码为 `g3 g2 g1 g0`：

```text
g3 = b3
g2 = b3 XOR b2
g1 = b2 XOR b1
g0 = b1 XOR b0
```

每一位的格雷码都等于自己和更高一位的二进制位做异或运算 `^`

### 怎么理解 i >> 1

道理看起来是很容易懂，但是一到写具体的代码，总是会出现各种各样的问题，那么这里的一大问题就是如何理解 `i >> 1`，我们以 3 位二进制数 `101` 为例，看看到底发生了什么：

```bash
101 >> 1 ==> 010
                      b3 b2 b1
101 ^ 010
==>
g2 = b3 ^ b2 = 0 ^ 1 = 1
g1 = b2 ^ b1 = 1 ^ 0 = 1
g0 = b1 ^ b0 = 0 ^ 0 = 1
==> G(3) = 111
```

我们可以发现，因为向右移一位使刚才的最高位变成了 0，做异或运算时结果只取决于 `b2` 即原最高位的值，这样我们就做出了更高一位的错位。注意我们这里是向右移位，把高位错到低位上与自己做运算，这一步说实话还是有点难想的

```c++
int BinaryToGray(int n) {
  return (n >> 1) ^ n;
}

vector<int> grayCode(int n) {
  vector<int> ret(1 << n);
  for (int i = 0; i < ret.size(); i++) {
    ret[i] = (i >> 1) ^ i;
  }
  return ret;
}
```

对于循环码排列，只需要进行一点点的修改：

```c++
ret[i] = (i >> 1) ^ i ^ start;
```

我们只要异或上 `start` 就能确定格雷码序列的开始位置，在格雷码中，可以认为异或是一种移位操作，它不会改变格雷码序列本身的性质，但是会以某种规律改变序列的排序，但总之无论你怎么做，它都会在这个框架内有规律地变化，异或一个数字，就像移动格雷码序列环上的指针到这个数字上

## 格雷码逆推二进制

$$
b_i = b_{i+1} \ \mathrm{XOR}\ g_i
$$

```c++
int GrayToBinary(int g) {
  int mask = g;
  while (mask) {
    mask = mask >> 1;
    g = g ^ mask;
  }
  return g;
}
```

逆推有个特点，就是我们可以一路递推：

$$
b_i = g_i \ \mathrm{XOR}\ g_{i+1}\ \mathrm{XOR}\ g_{i+2}\ \mathrm{XOR}\ \cdots\ \mathrm{XOR}\ g_{n-1}
$$

直到最高位 $g_{n-1} = b_{n-1}$，因此我们只要不断做移位操作然后异或，类似于差分

```text
初始: g = 0110, mask = 0110

① mask >>= 1 → 0011
   g ^= mask → 0110 ^ 0011 = 0101

② mask >>= 1 → 0001
   g ^= mask → 0101 ^ 0001 = 0100

③ mask >>= 1 → 0000 → 结束

返回 g = 0100 ✅
```

```text
格雷码:   g3 g2 g1 g0
          ↓  ↓  ↓  ↓
          0  1  1  0
           ↘ ↘ ↘
第一次传播:   0  1⊕1  1⊕0
                ↓     ↓
第二次传播:      0⊕1⊕1  1⊕1⊕0
结果(二进制):   0  1  0  0
```

这个算法，没有公式为基础，光靠脑袋想还是挺有难度的
