这道题应该是考察 grey code 的概念。
格雷码是怎么来的？二进制数011，加1的时候变成100，在老式装置上，这意味着三个位元都要转动，增加了出错的几率。在这种情况下，人们发明了格雷码。
所以很显然，格雷码的特征是：每次加一，只改变一位。
直观的看，三位格雷码列表：
| 十进制 | 格雷码 | 二进制 |
|---|---|---|
| 0 | 000 | 000 |
| 1 | 001 | 001 |
| 2 | 011 | 010 |
| 3 | 010 | 011 |
| 4 | 110 | 100 |
| 5 | 111 | 101 |
| 6 | 101 | 110 |
| 7 | 100 | 111 |
这个顺序与题意的顺序一致，可以看到最后一个格雷码100与第一个格雷码000也只相隔一位。这种也叫做循环格雷码。
我们是根据什么依据产生这种格雷码的呢？从这幅图应该可以看出端倪：
首先是上下对称复制，然后分别冠以0与1. 随着位数的增加，不断重复这个过程。
这样的格雷码与二进制之间有着这样一个公式：从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值，最左边一位不变(相当于左边是0)。
简单表达为：the nth Gray code is obtained by computing (n/2) ^ n.
我的解法也是利用了这个公式。但对于该公式的证明，我却没有想的很明白。
#include <vector>
using std::vector;
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> vec;
for (int i = 0; i != 1<<n; ++i)
vec.push_back(i/2^i);
return vec;
}
};