算法

(位运算) $O(n)$

最简单的做法是利用位运算

一个数字对应的格雷编码的计算方式是：

• 将其二进制第一位(从高位数开始)与0异或, 得到的结果为格雷码的第一位
• 之后依次将原数的第 i 位与生成的格雷码第i-1位做异或运算, 即可得到格雷码的第i位

C++ 代码

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans(1<<n);
        for (int i = 0; i < 1<<n; ++i) {
            ans[i] = i ^ (i>>1); 
        }
        return ans;
    }
};