89. Gray Code (Medium)

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.

Solution 1: binary to gray code

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

Convertion of grey code and binary 格雷码和二进制数之间的转换

/*
        The purpose of this function is to convert an unsigned
        binary number to reflected binary Gray code.

        The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}

/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}

Solution 2: mirror relection

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;
}

Solution 3:

维基百科上还有一条格雷码的性质是直接排列，以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。根据这条性质也可以写出代码，不过相比前面的略微复杂，代码如下：