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.

Solution:

可以看到n位的格雷码由两部分构成，一部分是n-1位格雷码，再加上 1<<(n-1)和n-1位格雷码的逆序的和。 

1位格雷码有两个码字
(n+1)位格雷码中的前2^n个码字等于n位格雷码的码字，按顺序书写，加前缀0 
(n+1)位格雷码中的后2^n个码字等于n位格雷码的码字，按逆序书写，加前缀1。

由于是二进制，在最高位加0跟原来的数本质没有改变，所以取得上一位算出的格雷码结果，再加上逆序添1的方法就是当前这位格雷码的结果了。

当n=1时，0，1

当n=2时，原来的list 0，1不变，只是前面形式上加了个0变成00，01。然后加数是1<<1为10，依次：10+1=11 10+0=10。结果为：00 01 11 10

当n=3时，原来的list 00,01,11, 10（倒序为：10，11，01，00）。加数1<<2为100。倒序相加为：100+10=110, 100+11=111,100+01=101, 100+00= 100。

最终结果为[000,001,011,010,110,111,101,100]

算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。

public class Solution {
    public ArrayList grayCode(int n) {
        ArrayList res = new ArrayList();
        
        if(n < 0) {
            return res;
        }
        if(n == 0) {
            res.add(0);
            return res;
        }
        
        res.add(0);
        res.add(1);
        for(int i = 2; i <= n; i++) {
            //不需要处理前半部分，因为要求的是二进制数对应的整数，所以在前面加0等于原来的数字，
            //所以前面数字只需要保持原来就行，后面进行倒序然后对最高位赋1即可
            int size = res.size();
            for(int j = size - 1; j >= 0; j--) {
                res.add(res.get(j) + (1 << (i - 1)));
            }
        }
        return res;
    }
}

java中有三种移位运算符

<<      :     左移运算符，num << 1,相当于num乘以2

>>      :     右移运算符，num >> 1,相当于num除以2

>>>    :     无符号右移，忽略符号位，空位都以0补齐

43210      位数
--------
 1010      十进制：10     原始数         number
10100      十进制：20     左移一位       number = number << 1;
 1010      十进制：10     右移一位       number = number >> 1;

Reference: http://www.cnblogs.com/springfor/p/3889222.html

Reference: http://blog.csdn.net/linhuanmars/article/details/24511221