格雷编码

来源Leetcode第89题格雷编码

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

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

---

套公式

其实看题目描述会吐槽这是什么玩意，但是格雷码是数电里出现过的。
数电第一章1.4.2节格雷码公式：
设二进制数B = Bn-1 Bn-2 …… B1 B0
则其格雷码 G = Gn-1 Gn-2 …… G1 G0
且 Gn-1 = Bn-1
Gi = Bi+1 ^ Bi
即最高位保留，其它位是当前位和它的高一位进行异或操作。
而在这题中，题目是输入 n 代表n位二进制位，输出其编码系统。

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