一、介绍

典型的二进制格雷码（Binary Gray Code）简称格雷码，因1953年公开的弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication”而得名，当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。法国电讯工程师波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。

格雷码（Gray code）曾用过Grey Code、葛莱码、葛兰码、格莱码、戈莱码、循环码、二进制反射码、最小差错码等名字，它们有的是错误的，有的易与其它名称混淆，建议不再使用它们。

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。 [2] 在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

二、格雷码的计算

方法一：归纳法

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        ret.reserve(1 << n);
        ret.push_back(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m - 1; j >= 0; j--) {
                ret.push_back(ret[j] | (1 << (i - 1)));
            }
        }
        return ret;
    }
};

方法二：公式法

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

三、以指定格雷码作为首部元素的格雷码序列

只需在第二步的运算中，增加一步异或操作即可。

方法一：归纳法

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        ret.reserve(1 << n);
        ret.push_back(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m - 1; j >= 0; j--) {
                ret.push_back(ret[j] | (1 << (i - 1)));
            }
        }
        return ret;
    }
};

方法二：公式法

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> ret(1 << n);
        for (int i = 0; i < ret.size(); i++) {
            ret[i] = (i >> 1) ^ i ^ start;
        }
        return ret;
    }
};