89. Gray Code

题目描述：给非负整数 n 表示二进制位数，输出所有的 n 位格雷码，以0开始。

分析：时间复杂度O(2^n)，空间O(1)。

代码：用格雷码的数学公式将0 ～ 2^n - 1的所有整数转化为格雷码。公式为：整数 n 的格雷码是 n xor (n / 2)，即 n 与 n 的一半异或。异或位运算：

• 与0异或的结果还是原数
• 与1异或 的结果是每位变为其相反数

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        int sz = 1 << n;
        ans.reserve(sz);             //reserve函数用来给vector预分配存储区大小，但没有给这段内存进行初始化。即reserve 函数分配出来的内存空间，只是表示vector可以利用这部分内存，但vector不能有效地访问这些内存空间，访问的时候就会出现越界现象，导致程序崩溃。故不能用v[i]这种下标访问
        for (int i = 0; i < sz; i ++)
            ans.push_back( btog(i) );
        return ans;
    }
    int btog(int n)          //二进制数转化为格雷码
    {
        return n ^ (n >> 1);
    }
};