Create 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.

网上找的：分析的比较全，思路有了做很快，注意有15行 newNumber |= step; 表示两个数位运算
newNumber = newNumber|step;   step 比他高一位，高的一位位一，其余的都为0，所以用位运算更快捷。
分析：
格雷码的序列中应包含2^n个数。这个问题初看起来不容易，我们要想出一个生成方法。

对于n=2,序列是：
00，01，11，10
那对于n=3,如何利用n=2的序列呢？一个方法是，先在n=2的四个序列前加0（这其实是保持不变），然后再考虑把最高位变成1，只需要把方向反过来就可以了
000，001，011，010
100，101，111，110－> 110,111,101,100
把这两行合起来就可以得到新的序列。

想通了，写代码就很容易了。

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(0);
        if(n>0){
            result.add(1);
        }
        
        int mask = 1;
        for(int i=2;i<=n;++i){
            mask *= 2;
            for(int j=result.size()-1;j>=0;--j){
                int v = result.get(j).intValue();
                v |= mask;
                result.add(v);
            }
        }
        return result;
    }
}