格雷码 题解 FROM CSDN

1. 首先明白题意,题的意思就是,生成n位的格雷码,然后有编号,求编号为k的那个二进制串(先放栈里面,然后放在bin里面就是二进制);
2. 此题通过上面的一堆文字分析可以得到一个规律,把k变为二进制,然后结果就是每一位和左边一位做异或操作(相等为0，不相等为1),当然此题也可以按照题目描述来做,依次确定每一位的字符,但本质上两种方法是一样的:,每一位只和自己和它左侧那一位的影响。
3. 比如输入的是3 5，那么会产生000，001，011，010，110，111，101，100，编号依次为 0 ~ 7，这八个二进制串，我们求编号为5的，也就是111；然后我们把k转为二进制即：0101，然后依次比较当前位和上一位（异或），可得一个串：111，就是想要输出的结果；
4. 需要判断需要是否要补前导0（因为有可能n>idx），所以需要在前面补0，样例3 3 通过规律得到的串为10，但是题目让输出n位，所以前面补n-idx个零，不然直接输出就是100，不对
5. 然后就是精度问题，题目上的k最大是2^64，所以要用ULL；LL就会一个点过不去；

AC代码+注释

#include<bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
int n, idx;
ull k;
int bin[100];
int ans[100];
stack<int> s;

int main() {
    cin.tie(0);
    cin >> n >> k;
    //将k转为二进制
    while (k > 0) {
        s.push(k % 2);
        k /= 2;
    }
    while (!s.empty()) {
        bin[++idx] = s.top();
        s.pop();
    }
    //idx为k的二进制位数，逐个去判断
    for (int i = 1; i <= idx; ++i) {
        //异或
        if (bin[i] == bin[i - 1]) {
            ans[i] = 0;
        } else {
            ans[i] = 1;
        }
    }
    //样例3 3 通过规律得到的串为10，但是题目让输出n位，所以前面补n-idx个零
    for (int i = 1; i <= n - idx; ++i) {
        cout << 0;
    }
    //输出idx个有效位数
    for (int i = 1; i <= idx; ++i) {
        cout << ans[i];
    }
}