---

格雷编码

二进制运算

1.题目

89. 格雷编码 - 力扣（LeetCode）
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。

格雷编码序列必须以 0 开头。

示例 1:

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。

2.思路分析

见题解

3.所用到的方法

位移运算符 <<、>>
异或运算符 ^

1.交换律：a ^ b ^ c <=> a ^ c ^ b
2.任何数于0异或为任何数 0 ^ n => n
3.相同的数异或为0: n ^ n => 0

4.题解及优化

我的题解(!!!)

观看了一个简短的python解法如下：

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        n=1<<n
        res=[]
        for i in range(n):
            res.append(i^(i>>1)) #2进制转换格雷码
        return res

感觉这才是我想要的答案，使用js模仿如下

var grayCode = function (n) {
  n = 1 << n
  let res = []
  for (let i = 0; i < n; i++) {
    res.push(i ^ (i >> 1))  // 2进制转换格雷码
  }
  return res
}

还不错

课程解法

var grayCode = function (n) {
  // 递归函数，用来算输入为n的格雷编码序列
  let make = (n) => {
    if (n === 0) {
      return [0]
    } else if (n === 1) {
      return ['0', '1']
    } else {
      let prev = make(n - 1)
      let result = []
      let max = Math.pow(2, n) - 1
      for (let i = 0, len = prev.length; i < len; i++) {
        result[i] = `0${prev[i]}`
        result[max - i] = `1${prev[i]}`
      }
      return result
    }
  }
  return make(n).map(item => parseInt(item, 2))
}

其他小伙伴的解法

在十进制数组中找规律（1）

比如输入3,结果是[0,1,3,2,6,7,5,4]
总数就是2^3=8；
把它分成两部分，[0,1,3,2]和[6,7,5,4]，
然后把[0,1,3,2]复制一份，倒过来[2,3,1,0]
[6,7,5,4]减去[2,3,1,0]等于[4,4,4,4]=2的n-1次方遍历4次！

var grayCode = function(n) {
  let res = [0]
  let right
  for (let i = 1; i <= n; i++) {
    right = [...res].reverse().map((item) => item + Math.pow(2, i - 1))
    res = res.concat(right)
  }
  return res
}

---

在十进制数组中找规律（2）

n = 0, [0]
n = 1, [0,1] //新的元素1，为0+2^0
n = 2, [0,1,3,2] // 新的元素[3,2]为[0,1]->[1,0]后分别加上2^1
n = 3, [0,1,3,2,6,7,5,4] // 新的元素[6,7,5,4]为[0,1,3,2]->[2,3,1,0]后分别加上2^2->[6,7,5,4]
最终肯定会输出整个数组， 0 - 2^n-1

var grayCode = function(n) {
  let res = [0]
  let right
  let i = 1
  while (i <= n) {
    right = res
      .slice(0)
      .reverse()
      .map((item) => item + Math.pow(2, i - 1))
    res = res.concat(right)
    i++
  }
  return res
}

---

转码

时间复杂度: O(2^N)
空间复杂度: O(1)

var grayCode = function(n) {
    let ans = [];
    let head = 1;
    ans.push(0);
    for(let i = 0; i < n;i ++) {
        let len = ans.length - 1;
        for(let j = len; j >=0; j--) {
            ans.push(head + ans[j])
        }
        // 位运算: b1等于b1乘以2的1次方
        head <<=1;
    }
    return ans;
};

拓展

• 格雷码与二进制代码的转换规则 - 百度文库