題目描述:兩個整數的漢明距離(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:
__builtin_popcount(x ^ y) — 編譯器直接對應到硬體指令(如 x86 的 POPCNT),最為高效。n &= (n - 1) 每次消去最低位的 1,迴圈次數等於 1 的個數。兩種方法時間複雜度均為 O(1)(整數位元固定為 32 位)。
時間複雜度: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 稍慢(視編譯器優化而定)。適合追求可移植性而非極致效能的場合。
n & (n - 1) 為什麼能消去 n 的最低位 1?請用 4 位元的例子(如 n = 1100)從二進位角度說明補數相減的原理。