格雷编码

n 位格雷码序列 是一个由 2^n 个整数组成的序列，其中：

每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 1）

第一个整数是 0

一个整数在序列中出现不超过一次

每对相邻整数的二进制表示恰好一位不同 ，且第一个和最后一个整数的二进制表示恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列。

Input:n = 2

Output: [0,1,3,2]

解释：

[0,1,3,2] 的二进制表示是 [00,01,11,10] 。

- 00 和 01 有一位不同

- 01 和 11 有一位不同

- 11 和 10 有一位不同

- 10 和 00 有一位不同

[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。

- 00 和 10 有一位不同

- 10 和 11 有一位不同

- 11 和 01 有一位不同

- 01 和 00 有一位不同问题分析：

格雷码序列我们可以这样理解，把 [0, 2^n - 1] 中所有数字串成一个环，环中每相邻两数字的二进制位有且仅有一位不同。其中格雷码的第一个整数是 0 。我们来看下几个格雷码的特点，如下表所示。

1 位格雷码2 位格雷码3 位格雷码3 位二进制数4 位格雷码4 位二进制数

00000000000000000

10100100100010001

1101101000110010

1001001100100011

11010001100100

11110101110101

10111001010110

10011101000111

11001000

11011001

11111010

11101011

10101100

10111101

10011110

10001111

通过上面的表格，可以发现一个规律就是 n 位格雷码长度是 n+1 位格雷码长度的 1/2 。如果知道 n 位格雷码，只需要在他们前面都加上 0 就是 n +1 位格雷码的前半部分，逆序在最前面加上 1 就是 n+1 位格雷码的后半部分。举个例子，比如 2 位格雷码有 [00，01，11，10]，在前面加上 0 就是 [000，001，011，010]，逆序在最前面加上 1 就是 [110，111，101，100]，他们加起来就是[000，001，011，010，110，111，101，100]，这个就是 3 位格雷码。同理根据 3 位格雷码，我们也可以计算出 4 位格雷码。。。

总结如下：

1 位格雷码只有 0 和 1 两个数字。

n 位格雷码在前面加上 0 就是 n+1 位格雷码的前半部分。

n 位格雷码的逆序，在前面加上 1 就是 n+1 位格雷码的后半部分。

实际上这题返回的不是二进制，而是一个整数，对于一个整数来说前面加上 0 并不会改变他的值，比如二进制 11 和二进制 011 都是 3 。所以如果知道 n 位格雷码，我们只需要计算 n+1 位格雷码的后半部分即可，前半部分就是 n 位格雷码的值。

public List<Integer> grayCode(int n) {

List<Integer> res = new ArrayList<>();

res.add(0);// 默认第一个是 0 。

for (int i = 0; i < n; i++) {

// 前半部分不变，只计算后半部分即可，

int mask = 1 << i; // 前面是 1 。

// 注意这里要逆序遍历，在最前面加 1 。

for (int j = res.size() - 1; j >= 0; j--)

res.add(res.get(j) | mask);// 前面变成 1 。

}

return res;

}

解法二：

我们知道 n 位格雷码总共有 2^n 个，比如 3 位格雷码有 8 个，4 位格雷码有 16 等。仔细观察从 0 到 2^n -1 这些数字和格雷码之间的规律，就会发现：

格雷码的最高位和这些数字二进制的最高位是相同的，

对 n 位二进制数（从右到左，以 1 到 n 编号），如果二进制的第 i 位和 i+1 位相同，则对应的格雷码的第 i 位为 0 ，否则为 1 。

对于一个二进制数字，只需要保证最高位不变，其他相邻的两位异或即可得到对应的格雷码。相邻两位 异或 有两种实现方式，一种是 i^(i<<1) ，一种是 i^(i>>1) ，如果还要保证最高位不变，只能选择 i^(i>>1) 。因为往右移的时候， i>>1 的第 n 位变成了 0 ，如果原来二进制数的第 n 位是 0 ，它与 0 异或结果还是 0 ，如果原理二进制数的第 n 位是 1 ，它与 0 异或结果还是 1 。

public List<Integer> grayCode(int n) {

List<Integer> res = new ArrayList<>();

int size = 1 << n;// n 位总的格雷码个数。

for (int i = 0; i < size; i++)

res.add(i ^ (i >> 1));// 根据当前数字计算对应的格雷码

return res;

}