LeetCode : Gray Code #89

刷着刷着学到了新的姿势，这个体位在EE上面很有用，做个简单的记录。

Question

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.

Analysis

这道题是实际上是考察是否了解格雷码，并且对于bitwise operation的了解程度。

格雷码

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。

在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。

在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

格雷码原理

格雷码实际上就是把原数字A的二进制向右移一位变成B，然后A xor B得出来结果。

下面就是格雷码的递推表格。

2位格雷码	3位格雷码	4位格雷码	4位自然二进制码
00 01 11 10	000 001 011 010 110 111 101 100	0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

于是我们只需要把输入的数字 >>1 再 xor，就可以得到对应的格雷码。

Solution

解法一(Java)

public class Solution {
    public List<Integer> grayCode(int n) {
        List answerList = new ArrayList();
        for(int i=0;i<Math.pow(2,n);i++) answerList.add(i ^ (i >> 1));
        return answerList;
    }
}

Information

/*
 * This function converts an unsigned binary
 * number to reflected binary Gray code.
 *
 * The operator >> is shift right. The operator ^ is exclusive or.
 */
public int binaryToGray(int num)
{
    return num ^ (num >> 1);
}

/*
 * This function converts a reflected binary
 * Gray code number to a binary number.
 * Each Gray code bit is exclusive-ored with all
 * more significant bits.
 */
public int grayToBinary(int num)
{
    int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}

Reference

Gray Code #89 - LeetCode

Gray code - Wikipedia

LeetCode : Gray Code #89 - Github