解題說明
Hamming Distance
題目描述：兩個整數的漢明距離（Hamming Distance）是它們的二進位表示中，對應位元不同的數量。給定兩個整數 x 和 y，計算並回傳它們的漢明距離。例如 x = 1（0001），y = 4（0100），不同位元有 2 個，答案為 2。
解題思路：XOR + 計算位元 1 的個數。
-
XOR 定位差異：
x ^ y的結果在x和y位元不同的位置為 1，相同的位置為 0。因此漢明距離 =x ^ y中 1 的個數（即 popcount / population count）。 -
計算 popcount：
- C++ 內建函數：
__builtin_popcount(x ^ y)— 編譯器直接對應到硬體指令（如 x86 的POPCNT），最為高效。 - Brian Kernighan's Algorithm：
n &= (n - 1)每次消去最低位的 1，迴圈次數等於 1 的個數。
- C++ 內建函數：
兩種方法時間複雜度均為 O(1)（整數位元固定為 32 位）。
C++ 解法
複雜度分析
時間複雜度：O(1) — 整數固定為 32 位元，XOR 和 popcount 操作的步驟數有常數上界（最多 32 次迭代），與輸入值的大小無關。
空間複雜度：O(1) — 只使用常數個額外變數。
虛擬碼
Function hammingDistance(x, y):
xorVal = x XOR y // 不同位為 1
// 方法一：直接使用 popcount
Return popcount(xorVal)
// 方法二：Brian Kernighan's Algorithm
// count = 0
// While xorVal != 0:
// xorVal = xorVal AND (xorVal - 1) // 消去最低位 1
// count = count + 1
// Return count其他解法
逐位掃描法 O(1)：對 x ^ y 逐位右移（共 32 次），每次檢查最低位是否為 1（n & 1），累計計數。與 Brian Kernighan's Algorithm 相比，此法固定執行 32 次，後者只執行與 1 的個數等量的次數，在 1 較少時更快。
查表法 O(1)：預先建立大小 256 的表，記錄 0–255 每個數字的 popcount。對 32 位整數分成 4 個 byte，查表後相加。常用於嵌入式或無 POPCNT 指令的環境，以空間換取運算速度的穩定性。
std::bitset 法：bitset<32>(x ^ y).count() — 標準函式庫提供的 popcount，可讀性高，但通常比 __builtin_popcount 稍慢（視編譯器優化而定）。適合追求可移植性而非極致效能的場合。
延伸思考
- LeetCode 477「Total Hamming Distance」要求計算陣列中所有整數對的漢明距離總和，逐對計算為 O(n²)，有沒有 O(n × 32) 的解法（逐位元統計 0 和 1 的個數）？
- 漢明距離等於 1 代表兩個二進位字串只差一個位元翻轉。在密碼學和通訊中，漢明距離有哪些應用（如錯誤偵測與糾錯碼）？
n & (n - 1)為什麼能消去n的最低位 1？請用 4 位元的例子（如n = 1100）從二進位角度說明補數相減的原理。