目標：
這篇的目標是介紹Gray Code以及二進位的位元運算部分。

原題：

Question:
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.

Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

分析/解題：
格雷碼是一個二進位表示的編碼系統，當中每個連續(相鄰)的二個值之間的表示方式只會相差一個位元(bit)。題目給定n個bits，試求出其表達的格雷碼序列。(格雷碼序列一定是從0開始)

在這邊簡單講解一下Bitwise Operation。
(註:本題雖然不會用到太多，
但熟悉這些操作對於一些題目和實際應用上很有幫助，
故在此先行列出給讀者學習。)

先前的文章中已經提到了，電腦對於二進位制的東西操作起來是較為得心應手的，
當然我們可以不用像電腦這麼熟悉，但只要會用就可以了XD
二進位之間的一些操作運算，就像是邏輯學上的運算一樣，
有AND/OR/NOT/XOR，以及位移運算(bit shifts)等，
這些速度在相同狀況下是由CPU進行支援的，運算速度往往會比一般的四則運算還快。

AND(且):
邏輯上的AND，代表著前後皆為真的狀況結果才為真，否則為假，
也就是兩者皆成立才行。在位元運算中，1被視為真，0被視為假。
(所以在如C/C++中你可能會看到使用IF 1或IF 0的開關)
延伸到多個bit的狀況，就是將前後兩者每個bit兩兩相對，
當兩者為1時，運算完的那個新的bit為1，否則為0。
如 110 AND 100的結果會是100(只有最左邊的bit是兩個1)
Java和Python中的AND運算符號均為"&"。
(請留意，如果判斷兩個運算結果的是否為真的邏輯運算，
Java是"&&"，Python則是"and"，
以位元為基準的運算和求真偽的邏輯運算是不同的，記得不要搞混了！)

OR(或):
前後兩者只要其一為真結果即為真，
也就是只有兩者皆不成立時，結果才會是假。
所以在位元運算中，
兩兩相對，除了兩個bit都是0的運算結果是0外，其餘都會是1。
如 110 OR 100的結果會是110(只有最右邊的bit是兩個0)
Java和Python中的OR運算符號均為"|"。
(如果是邏輯運算的話，Java是"||"，Python則是"or")

NOT(非):
邏輯上的NOT，代表將該真/假狀況轉為原先的相反，
真的變假的，假的變真的。
在位元運算中，對每個bit操作，
只要原先是1的均變為0，為先為0的則變為1。
如NOT 110的結果會是001。
Java和Python中NOT運算符號均為"~"。
(如果是邏輯運算的話，Java是"!"，Python則是"not")

XOR(互斥或，Exclusive OR):
邏輯上的XOR，代表前後兩個狀況剛好有一個成立時為真，
即前真後假/前假後真，其餘皆為假。
位元運算的部分，兩兩相對檢查，當發現是一個1一個0的時候，
結果為1，否則均為0。
如1100 XOR 1010的結果會是0110。
Java和Python中的XOR運算符號均為"^"。

位移運算:
將一個數的所有bit的東西往左或往右移動指定的位元數，
超出儲存空間的部分捨棄，被位移走的原處則補0。
Java和Python中使用"<<"和">>"分別代表向左位移及向右位移。
例如:
2 << 1 的結果會是4，因為2的二進位是"10"，
這個操作代表2向左位移1個bit，空白的部分補零，
所以會得到"100"也就是十進位制的4。

9 >> 2的結果會是2，因為9的二進位是"1001"，
這個操作代表向右位移2個bit，所以"01"的部分移出儲存範圍了被捨棄掉，
會得到"10"，也就是十進位的2。

直觀上我們可以將位移N個bit視作乘以或除以2的N次方，
但要注意範圍是否正確，以及是否要處理正負號的部分。

上面介紹了位元運算以後，讓我們回到題目。
在通訊傳輸的過程中，有可能因為受到雜訊干擾等狀況，
使得當中的位元反轉(0變成1，1變成0)。倘若我們按照正常的表達方式，
例如7=0111, 8=1000，對於某些臨界狀況而言，
小範圍的變動值會需要大幅度的修改bit，同時當某個高位數的bit出錯的狀況，
值就有可能受到大幅度的改變，這顯然是比較糟糕的。

所以格雷碼的設計就是希望能夠讓更動小數值的時候，
只更動較少的bit數量即可，且當有其中的bit受到干擾而出錯時，
數值的影響範圍也較小。

那怎麼計算呢？
我們從1個bit開始推導看看：
由於要求要從0開始，
故我們應該是拿0代表0，1代表1，這樣就完成了1個bit的格雷碼。
2個bit的話，由於用10來表示會一次更動2個bit(01->10)，
所以我們只能拿11來表示2，而10則表示3。

00 - 0
01 - 1
11 - 2
10 - 3 

當然，也可以用00, 10, 11, 01來進行表示，但這種方式相對較複雜，
我們直接去考慮前面的方式的邏輯就好。

再來我們可以思考，在不要動到前面的數的狀況下，
下面我們要怎麼表達3個bit的狀況呢？
已經知道：

000 - 0
001 - 1
011 - 2
010 - 3

我們想要剛好用3個bit表示0~7，
那唯有讓4~7的部分的最左邊的bit均為1才行。
(因為前面的2個bit組合已經被用過了)
同時我們又想要符合相鄰只動一個bit的原則，
所以4的表示方式就只剩下110了!

000 - 0
001 - 1
011 - 2
010 - 3
110 - 4
1xx - 5
1xx - 6
1xx - 7

同時，我們也知道前面0~3符合這個只動一個bit的表達方式，
那麼後面填入5~7的方式，就可以按照上下鏡向的狀況填入，
自然會符合格雷碼的要求。也就是除了最左邊是1以外，
4對應到3，5就對應到2，6對應到1，7對應到0即可。

000 - 0
001 - 1
011 - 2
010 - 3
110 - 4
111 - 5
101 - 6
100 - 7

同樣的道理，變成4個bit時，將後面的8個數的最左邊的bit填入1，
其它的部分鏡向填入即可。

歸納一下這題的解法：

1. 先放入0(最開始的部分，也是n=0時的解答)
2. 定義一個變數adder，用來表示這輪要加上去的bit所代表的值
   (初始值是2的0次方=1)
3. 每次將答案的尾端加上一個新的值，
   這個新的值是鏡向對應到的值加上adder。
   (鏡向對應的方式，可以從尾端開始往回算，或者用adder-1-index來計算)
4. 計算完畢一輪以後，將adder變為2倍，作為下一輪要額外加上去的值。
5. 一路操作直到完成n輪為止，最後將結果回傳。

Java:

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        if (n > 0) {
            int adder = 1;
            for (int i = 1; i <= n; i++) {
                int len = res.size();
                for (int j = len - 1; j >= 0; j--) {
                    res.add(res.get(j) + adder);
                }
                adder *= 2;
            }
        }
        return res;
    }
}

Python:

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = [0]
        add = 1
        for _ in range(n):
            for i in range(add):
                res.append(res[add - 1 - i] | add);
            add <<= 1
        return res

讀者可以看到兩個解法中一個使用+adder，另一個使用|add，
結果上是一樣的，因為加上去的那個bit一定是跟0相加，
故可以用OR運算會加快一點速度。(讀者可以修改成+來比較看看速度)

• 2和<<=1的部分，同樣可以等價於位移一個bit，
  但速度上應該不會有特別差異才對。

面試實際可能會遇到的問題：
「時間複雜度？」
(O(2的n次方)，因為n個bit可以表示2的n次方個數)

「(Python)能不能不要用append來解？」
(可以用extend，
每次將res的部分反轉接上後，再進行add的加總)

「為什麼你要用"_"？」
(因為第一個迴圈事實上只是處理執行n次這件事情，
我們並不需要用到其數值，在習慣上會盡量用底線來命名，
避免去用到有意義的命名方式。)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0092. Reverse Linked List II (Medium)