Trick 2.1 - 找出最低 1-bit

給定一個整數 $$x$$，我們想要知道他的 low-bit，也就是最低的那個 1-位元在哪裡。讓我們觀察一下這個例子： $$x = (1100010000101000)_2$$，那麼我們可以發現 $$x-1 = (110001000010{\color{red}{0111}})_2$$

因此，若要拿出最低 bit，可以把 $$x-1$$ 反過來，然後做個 AND 運算：

    x    = 1100010000101000
~(x-1)   = 0011101111011000
----------------------------
x&~(x-1) = 0000000000001000

不過，厲害的地方是，不難發現，根據二的補數法，我們知道 ~(x-1) = -x，因此前述取出最小 bit 的步驟可以簡化為 x&-x。

格雷碼 Gray Code

所謂的 Gray Code，是指將 $$0$$ 到 $$2^n-1$$ 的排成一圈，使得相鄰兩數的二進位表示恰好相差一個 bit。例如 $$n=3$$ 的時候，我們可以找出一個 Gray Code：

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

我們有一個不需要遞迴、不需要記錄之前產生過哪些數字，就可以生成 Gray Code 的方法：注意到相鄰兩項的 XOR 值（標記在上面右邊），第 $$i$$ 個剛好就是把 $$i$$ 寫成二進位以後的 lowbit！因此，我們可以用一個 for 迴圈產生 Gray Code。

int now = 0;
for (int i = 0; i < (1<<n); i++) {
    now = now ^ (i&-i);
    cout << now << endl;
}