格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个二进制的差异。

给定一个非负整数 n ，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2n 个整数。

对于给定的 n，其格雷编码顺序并不唯一。
当n = 2时，根据上面的定义，[0,1,3,2] 和 [0,2,3,1] 都是有效的格雷编码顺序。
在线评测地址：
https://www.lintcode.com/problem/gray-code/?utm_source=sc-tc-sz0812
​
样例 1:

输入: 1
输出: [0, 1]
样例 2:

输入: 2
输出: [0, 1, 3, 2]
解释:
0 - 00
1 - 01
3 - 11
2 - 10
最简单的做法是利用位运算. 在《计算机组成与设计》一书上有介绍.

一个数字对应的格雷编码的计算方式是:

将其二进制第一位(从高位数)与0异或, 得到的结果为格雷码的第一位
之后依次将原数的第i位与生成的格雷码第i-1位做异或运算, 即可得到格雷码的第i位.
public class Solution {

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < (1 << n); i++)
        result.add(i ^ (i >> 1));
    return result;
}

}

////////// 递归版本

public class Solution {

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if (n <= 1) {
        for (int i = 0; i <= n; i++){
            result.add(i);
        }
        return result;
    }
    result = grayCode(n - 1);
    ArrayList<Integer> r1 = reverse(result);
    int x = 1 << (n-1);
    for (int i = 0; i < r1.size(); i++) {
        r1.set(i, r1.get(i) + x);
    }
    result.addAll(r1);
    return result;
}

public ArrayList<Integer> reverse(ArrayList<Integer> r) {
    ArrayList<Integer> rev = new ArrayList<Integer>();
    for (int i = r.size() - 1; i >= 0; i--) {
        rev.add(r.get(i));
    }
    return rev;
}

}
更多题解参见九章算法官网：
https://www.jiuzhang.com/solution/gray-code/?utm_source=sc-tc-sz0812