格雷编码模板

#include <bits/stdc++.h>
using namespace std;

// 镜像反射法生成格雷码
vector<int> grayCode(int n) {
    vector<int> res;
    res.push_back(0);
    for (int i = 0; i < n; i++) {
        int size = res.size();
        for (int j = size - 1; j >= 0; j--)
            res.push_back(res[j] | (1 << i));
    }
    return res;
}

// 二进制转格雷码：gray = n ^ (n >> 1)
int bin2gray(int n) { return n ^ (n >> 1); }

// 格雷码转二进制
int gray2bin(int gray) {
    int bin = gray;
    while (gray >>= 1) bin ^= gray;
    return bin;
}

int main() {
    int n = 3;
    auto codes = grayCode(n);
    for (int c : codes) {
        cout << bitset<3>(c) << " ";
    }
    // 000 001 011 010 110 111 101 100
    return 0;
}

📖 要点说明

• 格雷码性质：相邻两数只有一个二进制位不同
• 公式：gray = n ^ (n >> 1)
• 镜像法：每轮把已有编码镜像翻转，最高位加1

⚠️ 常见错误

• 格雷码转二进制的方向搞反
• n 位格雷码共 2^n 个
• 忘理解相邻只差一位的用途