格雷码的实现

  在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
 这是腾讯2016年校招试题，题目虽然不难，但要完全写对却也不易。这里根据网上找到的资料，把它总结一下。
 原题要求用递归，递归的算法思想如下：（以三位格雷码为例）
                   000 
                    001
                    011
                    010
                    110
                    111
                    101
                    100  
仔细观察，发现除了最高位（左边第一位），格雷码的位元完全上下对称。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。  所以整个算法完全可以用如下的递归步骤来实现：

第一步：产生 0, 1 两个字符串。

第二步：在第一步的基础上，每一个字符串都加上0和1，但是每次只能加一个，所以得做两次。这样就变成了 00,01,11,10 （注意对称）。

第三步：在第二步的基础上，再给每个字符串都加上0和1，同样，每次只能加一个，这样就变成了 000,001,011,010,110,111,101,100。

好了，这样就把3位元格雷码生成好了。

如果要生成4位元格雷码，我们只需要在3位元格雷码上再加一层0,1就可以了： 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.

贴一下代码
 
 

String[] GrayCode(int n) {

    // produce 2^n grade codes
    String[] graycode = new String[(int) Math.pow(2, n)];

    if (n == 1) {
        graycode[0] = "0";
        graycode[1] = "1";
        return graycode;
    }

    String[] last = GrayCode(n - 1);

    for (int i = 0; i < last.length; i++) {
        graycode[i] = "0" + last[i];
        graycode[graycode.length - 1 - i] = "1" + last[i];
    }

    return graycode;
}

关于递归的写法，网上有很多种形式，比如下面这种：

#include <iostream>
#include <string>
using namespace std;

void bitString(int x, string prefix)
{
    if (x == 0)
       cout << prefix << endl;
    else{
       bitString(x-1, (prefix+"0"));
       bitString(x-1, (prefix+"1"));
    }
}

int main()
{
     int n;
     cin >> n;

     bitString(n, "");
}

这样生成的“格雷码”是如下的形式：                        
       000   001   010   011   100   101   110   111                                                                       
 乍一看，似乎没有问题，仅仅只是顺序有些颠倒，但仔细看格雷码的定义，n位元的格雷码个数就是2^n，正好等于n位二进制数的个数，如果格雷码没有顺序，那就变成了二进制位的简单罗列，失去了编码的意义。        
  到了这一步不满足于仅仅把这道题做出来，于是又在网上搜索了一下，于是发现它居然是leetcode上一道题，好在leetcode上的题大神陈皓已经全都刷过了，这真是给了我这种算法菜鸟一个很好的学习资料，皓神对于Gray Code的理解是这样的：
有了这幅图，我想已经不需要再多说什么了，直接上代码吧！（图若不清楚，还请看原博客）

	* 0
	* __/ \__
	* 0 1
	* / \ / \
	* 0 1 1 0
	* So, the gray code as below: (top-down, from left to right)
	*
	* 0 0 0
	* 0 0 1
	* 0 1 1
	* 0 1 0
	*
	* 0
	* _____/ \_____
	* 0 1
	* __/ \__ __/ \__
	* 0 1 1 0
	* / \ / \ / \ / \
	* 0 1 1 0 0 1 1 0
	*
	* So, the gray code as below:
	*
	* 0 0 0 0
	* 0 0 0 1
	* 0 0 1 1
	* 0 0 1 0
	* 0 1 1 0
	* 0 1 1 1
	* 0 1 0 1
	* 0 1 0 0

    

vector<int> grayCode(int n) {
    vector<int> v;
    //n = 1<<n;

    int x =0;
    v.push_back(x);
    for(int i=0; i<n; i++){
        int len = v.size();
        for (int j=0; j<len; j++){
            x = v[j]<<1;
            if (j%2==0){
                v.push_back(x);
                v.push_back(x+1);
            }else{
                v.push_back(x+1);
                v.push_back(x);
            }
        }
        v.erase(v.begin(), v.begin()+len);
    }

    return v;
}

皓神最后提到，这题其实有最简单的方法，是维基上给出的（难怪腾讯的笔试题要求用递归），更加容易懂，直接贴代码
 

vector<int> grayCode(int n) {
    vector<int> ret;
    int size = 1 << n;
    for(int i = 0; i < size; ++i) {
        ret.push_back((i >> 1)^i);
    }
    return ret;
}

  到这一步格雷码的求法就结束了，但我认为不应当仅局限于此，从这道题我可以掌握很多位运算的技巧，而这正是我的薄弱之处，皓神还给出了如何打印格雷码的方法，例如：存储于int型数组的值0， 如果对应于三位的格雷码应该是“000”，贴一下他的代码：

void printBits(int n, int len){
    for(int i=len-1; i>=0; i--) {
        if (n & (1<<i)) {
            printf("1");
        }else{
            printf("0");
        }
    }
}

void printVector(vector<int>& v, int bit_len)
{
    vector<int>::iterator it;

    for(it=v.begin(); it!=v.end(); ++it){
        //bitset<bit_len> bin(*it);
        printBits(*it, bit_len);
        cout << " ";
        //cout << *it << " ";
    }
    cout << endl;
}

int main(int argc, char** argv)
{
    int n = 2;
    if (argc>1){
        n = atoi(argv[1]);
    }
    vector<int> v = grayCode(n);
    printVector(v, n);
    return 0;
}

参考资料：
           递归算法：http://blog.csdn.net/beiyeqingteng/article/details/7044471
           皓神的GitHub： />            如要彻底了解格雷码： style="color:#000000;font-size:18px;">