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
题意：这道题要求相邻两个数有且仅有一位不同，并且第一个和最后一个数也满足要求。
思路：好吧，由于本人本科是学通信的，一看到这道题就知道这是大名鼎鼎的格雷编码。其编码规则如下：
整数 二进制
格雷编码
0 000
000
1 001
001
2 010
011
3 011
010
4 100
110
5 101
111
6 110
101
7 111
100
对比格雷码和二进制可知，将二进制的最右边位开始，与其相邻的左一位异或，最左位保持不变，即可得到格雷编码，再将格雷编码转为数字，即满足题目要求。
class Solution {
public:
vector<int> grayCode(int n) {
/**************************************
* 格雷编码
* **********************************/
vector<int> aa;
int bit[32],i,j;
int result = 0;
int length = 1;
while(n--)
{
length *= 2;
}
for(i=0; i<length; i++)
{
result = 0;
bit[0] = i&1;
for(j=1; j<32; j++)
{
bit[j] = (i>>j)&1;
result += ((bit[j]^bit[j-1]) << (j-1));
}
result += (bit[j-1] << (j-1));
aa.push_back(result);
}
return aa;
}
};