最近一段時間一直在刷力扣題，除參加字節的七天刷題挑戰之外，其它時間大體按照算法模板分類訓練。
開頭的二叉樹、鏈表、棧和隊列三節基本沒有遇到什麼問題，如今來到了二進制小節。因為之前了解較少的緣故，我做這一類題目已經淪落到了每道題都要看題解的地步（悲）。於是打算寫篇博文記錄一下每道題目的思路，方便自己以後回顧。
136. 只出現一次的數字#
給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。
利用位運算的性質，0^a=a，a^a=0，所以使用初始的 0 將數組遍歷異或，最後剩下的即為只出現一次的元素。
package main
func singleNumber(nums []int) int {
result := 0
for _, value := range nums {
result ^= value
}
return result
}
137. 只出現一次的數字 2#
給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現三次。找出那個只出現了一次的元素。
這道題目比起上一道，雖然只做了一點改動，但難度顯著上升。
先回顧一下上一道題的思路：我們選擇對數組進行遍歷異或，是因為異或運算能保證對同一元素計算兩次後能夠返回初始狀態，即0=0^a^a。而這道題目中重複元素出現了三次，參照上一道題的思路，我們希望找到一種運算 @，對於任意數 a，使得：0 = 0@a@a@a。
進一步闡述上一道題的情況，設數字被記錄下來為 1，數字未被記錄為 0，通過異或運算，我們滿足了：
因此出現兩次的數字全部被抵消，最後剩下的是出現一次數字的記錄狀態，即為結果。
對於二進制數字，每位只能表示兩個狀態，不適用於我們的情況，因此我們可以考慮使用兩位二進制來表示結果中的某一位，從 00 出發，在遇到 3 次 a 後返回 00 狀態。
使用兩個變量表示這兩位（依次為 x、y），我們要求當且僅當第二次遇到 a 時，x 為 0^a；當且僅當第一次遇到 a 時，y 為 0^a。這樣即可最終抵消出現三次的數字，最後會處於 01 狀態，此時 y 為結果。
package main
func singleNumber(nums []int) int {
var x, y int
for _, value := range nums {
y = (y ^ value) & ^x
x = (x ^ value) & ^y
}
return y
}
260. 只出現一次的數字 3#
給定一個非空整數數組，除了兩個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。
設兩個只出現一次的元素為 a、b。使用第一題的思路，我們可以很輕鬆地求得 a^b 的結果，但如何分別求出來 a 和 b 呢？
考慮 a^b 的二進制表示中結果為 1 的位，這位為 1 說明 a 和 b 在該位的數值不同，通過利用結果為 1 的位，我們可以將 a 和 b 區分到兩個不同的組。而因為其它數都剛好出現兩次，故它們必定會成對被分配到同一個組中。這樣兩個組都相當於第一題，分別求解即可。
注：要看懂以下代碼，你需要知道：
- n&(n-1) 可以去掉 n 的二進制表示中最後一位 1。
- (n&(n-1))^n 可以得到 n 的二進制表示中最後一位 1。
package main
func singleNumber(nums []int) []int {
var diff int
for _, value := range nums {
diff ^= value
}
// 設結果為a、b,當前得到的diff是a^b的結果
// 取到diff的任意一位1（此處使用的是最後一位）
diff = (diff & (diff - 1)) ^ diff
result := []int{0, 0}
for _, value := range nums {
if value&diff == 0 {
result[0] ^= value
} else {
result[1] ^= value
}
}
return result
}
191. 位 1 的個數#
編寫一個函數，輸入是一個無符號整數（以二進制串的形式），返回其二進制表示中數字位數為 '1' 的個數（也被稱為漢明重量）。
過於簡單，不斷按位與並將參數右移，計算 1 的個數即可。
func hammingWeight(num uint32) int {
var count int
for num != 0 {
count += int(num & 1)
num >>= 1
}
return count
}
338. 比特位計數#
給定一個非負整數 num。對於 0 ≤ i ≤ num 範圍中的每個數字 i ，計算其二進制數中的 1 的數目並將它們作為數組返回。
這道題的簡單思路是遍歷 i，對每個 i 使用上一道題目的算法，但複雜度太高。為了簡單，我們可以使用動態規劃，只需找到遞推關係即可。
設數 i 中出現二進制數 1 的個數為 f (i)。
第一種遞推關係，顯而易見，數 i 中出現二進制數 1 的個數等於 i 右移一位的數中出現二進制數 1 的個數加上 i 的二進制表示中最後一位的值。例如：
3 二進制表示為11
1 二進制表示為1
f(3)=f(1)+1
---------------------------
4 二進制表示為100
2 二進制表示為10
f(4)=f(2)+0
第二種遞推關係其實同樣簡單，數 i 中出現二進制 1 的個數等於 i 的二進制表示中移除最後一位 1 後的數中出現二進制 1 的個數加上 1。例如：
3 二進制表示為11
2 二進制表示為10
f(3)=f(2)+1
---------------------------
4 二進制表示為100
0 二進制表示為000
f(4)=f(0)+1
二進制表示中移除最後一位 1 的方式已經在只出現一次的數字 3中提到過。
package main
func countBits(num int) []int {
result := make([]int, num+1)
for i := 1; i <= num; i++ {
result[i] = result[i>>1] + (i & 1)
// 或者result[i] = result[i & (i-1)] + 1
}
return result
}