[LeetCode] 89. Gray Code

轉自LeetCode

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>

這題是要找所謂的 gray code，也就是相鄰的數字，只會有一個 bit 是不一樣的(wiki)

有很多種解法，先來看第一種

首先利用 n 位元的 gray code，可以從 n-1 位元的 gray code 用鏡射的方式產生

這邊先釐清一個部分，以 n = 2 和 n = 3 來舉例

可以看到前面四個數字 : 00，01，11，10，其實等同於 000，001，011，010

用十進位表示都是 0，1，3，2

因此，當我們在做鏡射的時候，其實只要從後往前，將１放到 n-1 位元前，成為第n個位元，這樣就可以了

code 如下

這題還有公式解

gray code = (num / 2) XOR num
code如下