Gray Code

Problem

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.

---

Idea

• 自然二进制码转换为格雷码:g0 = b0 , gi = bi ⊕ bi−1

保留自然二进制码的最高位作为格雷码的最高位,格雷码次高位为二进制码的高位与次高位异 或,其余各位与次高位的求法类似。例如,将自然二进制码 1001,转换为格雷码的过程是:保留最 高位;然后将第 1 位的 1 和第 2 位的 0 异或,得到 1,作为格雷码的第 2 位;将第 2 位的 0 和第 3 位 的 0 异或,得到 0,作为格雷码的第 3 位;将第 3 位的 0 和第 4 位的 1 异或,得到 1,作为格雷码的 第 4 位,最终,格雷码为 1101。

• 格雷码转换为自然二进制码:b0 = g0 , bi = gi ⊕ bi−1

保留格雷码的最高位作为自然二进制码的最高位,次高位为自然二进制高位与格雷码次高位异 或,其余各位与次高位的求法类似。例如,将格雷码 1000 转换为自然二进制码的过程是:保留最高 位 1,作为自然二进制码的最高位;然后将自然二进制码的第 1 位 1 和格雷码的第 2 位 0 异或,得 到 1,作为自然二进制码的第 2 位;将自然二进制码的第 2 位 1 和格雷码的第 3 位 0 异或,得到 1, 作为自然二进制码的第 3 位;将自然二进制码的第 3 位 1 和格雷码的第 4 位 0 异或,得到 1,作为 自然二进制码的第 4 位,最终,自然二进制码为 1111。
• 格雷码有数学公式,整数 n 的格雷码是 n ⊕ (n/2)。
• 其实这题让求n bit的所有格雷码,也就是算0-2^n-1里所有整数转换成的格雷码。

---

Solution

---