主題
題目連結：
題目意譯：
給定一整數 n，你必須藉由以下若干次的操作來將其轉換成 0：
將 n 的二進位表示法中最右側的位元（即第 0 位元）改變其數值；
將 n 的二進位表示法中第 i 位改變數值，前提是第 i - 1 位元是 1，而第 i - 2 位元到第 0 位元都是 0。
回傳將 n 轉換成 0 最少所需的操作數。
限制：
0 ≦ n ≦ 10 ^ 9
範例測資：
範例 1：
輸入： n = 3
輸出： 2
解釋： 3 的二進位表示法為 "11"。
用第二種操作將 "11" -> "01"，因為第 0 個位元是 1。
用第一種操作將 "01" -> "00"。
範例 2：
輸入： n = 6
輸出： 4
解釋： 6 的二進位表示法為 "110"。
用第二種操作將 "110" -> "010"，因為第 1 個位元是 1 且第 0 位元到第 0 位元都是 0。
用第一種操作將 "010" -> "011"。
用第二種操作將 "011" -> "001"，因為第 0 個位元是 1。
用第一種操作將 "001" -> "000"。
解題思維：
首先，我們先來判斷最單純的兩個情況：
如果 n == 0，則不需要任何操作；
如果 n 是 2 的某個冪次，即在 n 的二進位表示法中只有一個位元是 1（假設其為第 i 位元），則需要 2 ^ (i + 1) - 1 次操作。
上面的第二個情況可以用數學歸納法證明。因為可以看到為了將第 i 位元改變狀態，我們會需要先將第 i - 1 位元變成 1、其後位元是 0（這邊次數是 2 ^ i - 1）；用一次操作把第 i 位元變成 0，再把第 i - 1 位元變回 0（因故又有 2 ^ i - 1 次操作）。詳細證明過程省略。
接下來「第二單純」的情況就是 n 的二進位表示法中只有兩個位元是 1（假設為第 i 位元和第 j 位元，其中 i > j）。可以看到這個情況其實有點像是在處理 n 是 2 的冪次，但是是在把第 i - 1 位元變成 1 的過程中做一半的感覺。
因此，我們可以繼續所述之過程把第 i - 1 位元變成 1 為止（除非 j 本來就是 i - 1 了），也就是：
將第 j + 1 位元設為 1，將第 j 位元變回 0。次數是 2 ^ (j + 1) - 1 + 1 = 2 ^ (j + 1)；
將第 j + 2 位元設為 1，將第 j + 1 位元變回 0。次數是 2 ^ (j + 2)；
……
將第 i - 1 位元設為 1，將第 i - 2 位元變回 0。次數是 2 ^ (i - 1)；
最後再
將第 i 位元設為 0，將第 i - 1 位元變回 0。次數是 2 ^ i。
因此總次數為
2 ^ (j + 1) + 2 ^ (j + 2) + …… + 2 ^ (i - 1) + 2 ^ i
那剩下的情況呢？有了以上基礎之後也變得單純了，因為現在我們可以在 n 的二進位表示法中找出最左側的兩個 1（假設是第 i 位元和第 j 位元，其中 i > j）。而這兩個 1 為了要變成上面「第二單純」的情況需要其餘的 1 都先被消掉。
因此此時我們會產生出一個子問題——(n - 2 ^ i - 2 ^ j) 變成 0 的所需最少次數。因此我們可以遞迴解出這個子問題之後再根據上面的敘述處理第 i 、 j 位元即可。
等等那為什麼不直接只在 n 的二進位表示法中找出最左側的第 i 位元，然後先做子問題 (n - 2 ^ i) 再來處理第 i 位元呢？
因為這樣一來，原本「第 j 位元」（即第二左側的那一個 1）會在子問題中先被消掉，但是我們本來大可以直接套用「第二單純」的情況來得到更少的操作數。因為正如先前所述，第 j 位元的存在可以視為是處理第 i 位元時做一半的感覺。
而為了處理第 i 、 j 位元，其餘的 1 是「不得不」消掉。所以子問題可以放心做，不會有所「浪費」。
因故我們只能每次取最左側的兩個 1 來得到新的子問題來遞迴解。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
