题解 | #生成格雷码#

这个题考察的是二进制的移位，当不是最高位的时候，就需要将格雷码编码后的结果向右移动 n-m-1 位，然后提取出该位的值。

// c++ version
class GrayCode {
public:
    string int2Gray(int num, int n, int m, int gray) {
        string ans = "";
        if (m == n) return ans;
        if (m == 0) {                                 // 取最高位，没有移位
            int tmp = num >> (n - 1);
            ans += to_string(tmp);
        } else {                                     // 不是最高位
            int tmp = gray >> (n - m - 1);
            tmp &= 1;
            ans += to_string(tmp);
        }
        return ans+=int2Gray(num, n, m+1, gray);
    }
    vector<string> getGray(int n) {
        vector<string> ans;
        int i = 0;
        while (i <= (pow(2, n)-1)) {
            int gray = i ^ (i >> 1);              // 格雷码编码方式
            ans.push_back(int2Gray(i, n, 0, gray));
            i++;
        }
        return ans;
    }
};