Gray Code

2016-04-04

问题描述

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:

//3位gray code
格雷码     二进制码
0 0 0       0 0 0
0 0 1       0 0 1
0 1 1       0 1 0
0 1 0       0 1 1
1 1 0       1 0 0
1 1 1       1 0 1
1 0 1       1 1 0
1 0 0       1 1 1

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.

思路

经典的格雷码（Gray Code）问题。

主要涉及两种：

二进制码转格雷码
格雷码转二进制码

编码：

二进制码 —> 格雷码：
从二进制码的最右一位开始，每一位与其前一位做异或操作（XOR），最左边的那一位保持不变（相当于跟0做异或）。最后得到格雷码。

解码：

格雷码 —> 二进制码：
从格雷码的左边第二位开始，每一位跟其右边的一位做异或操作（XOR），将结果替换原来的位，再接着做下去，最左边的那位不变。

Code

编码的操作可以简化为：

GCode = BCode ^ (BCode >> 1);

vector<int> grayCode(int n) {
    vector<int> res;
    
    for (int i = 0; i < pow(2,n); i++){
        cout << (i ^(i >> 1));
        res.push_back(i ^(i >> 1));
    }
    
    return res;
}