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 位二进制数 |
|---|---|---|---|---|---|
| 0 | 00 | 000 | 000 | 0000 | 0000 |
| 1 | 01 | 001 | 001 | 0001 | 0001 |
| 11 | 011 | 010 | 0011 | 0010 | |
| 10 | 010 | 011 | 0010 | 0011 | |
| 110 | 100 | 0110 | 0100 | ||
| 111 | 101 | 0111 | 0101 | ||
| 101 | 110 | 0101 | 0110 | ||
| 100 | 111 | 0100 | 0111 | ||
| 1100 | 1000 | ||||
| 1101 | 1001 | ||||
| 1111 | 1010 | ||||
| 1110 | 1011 | ||||
| 1010 | 1100 | ||||
| 1011 | 1101 | ||||
| 1001 | 1110 | ||||
| 1000 | 1111 |
通过上面的表格，可以发现一个规律就是 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;
}
