[Leetcode] Gray code 格雷码

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return[0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note: 
 For a given n, a gray code sequence is not uniquely defined.

For example,[0,2,3,1]is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

 题意：给定n表示格雷码的位数，打印格雷码序列。

思路：首先要明白什么是格雷码。在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。如当n=2时，每个数之间的格雷码只有一位不同。

方法一：利用二进制转格雷码的转化公式：(num>>1)^num，注：num是非负整数，>>是右移操作，^是异或。先将二进制数的个数转换成范围，然后利用公式即可。代码如下：

class Solution {
public:
    vector<int> grayCode(int n) 
    {
        vector<int> res;
        for(int i=0;i<pow(2,n);++i) //pow函数为以2为底的n次方
        {
            res.push_back((i>>1)^i);
        }    
        return res;
    }
};

其中第6行pow()函数可以变成先定义一个变量，然后用这个值带入

int num=1<<n;

方法二：来自Grandyang的博客。 n元格雷码可以从n-1位元的格雷码以上下镜像后加上新位元的方式快速得到

代码如下：

class Solution 
{
public:
    vector<int> grayCode(int n) 
    {
        vector<int> res{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;
    }
};

1）格雷码 转 二进制码（摘自百度百科）：

格雷码→二进制码（解码）：

从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。

公式表示：

（G：格雷码，B：二进制码）

原码：p[n:0]；格雷码：c[n:0](n∈N）；编码：c=G(p）；解码：p=F(c）；

书写时按从左向右标号依次减小，即MSB->LSB，编解码也按此顺序进行

例子来自JustDoIT

如果采集器器采到了格雷码：1010

就要将它变为自然二进制：

0 与第四位 1 进行异或结果为 1

上面结果1与第三位0异或结果为 1

上面结果1与第二位1异或结果为 0

上面结果0与第一位0异或结果为 0

因此最终结果为：1100 这就是二进制码即十进制 12

 2）

二进制码→格雷码（编码）：

此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：

1. 对n位二进制的码字，从右到左，以0到n-1编号
2. 如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）公式表示：

（G：格雷码，B：二进制码）

例如：二进制码0101，为4位数，所以其所转为之格雷码也必为4位数，因此可取转成之二进位码第五位为0，即0 b3 b2 b1 b0。

0 xor 0=0，所以g3=0

0 xor 1=1，所以g2=1

1 xor 0=1，所以g1=1

0 xor 1=1，所以g0=1

因此所转换为之格雷码为0111

注意：格雷码转二进制码和二进制码转格雷的区别：前者是异或后的值再和下一位异或，后者是直接两相邻元素异或。