LeetCode 第 461 題“漢明距離”是一道經典的位運算問題，旨在計算兩個整數在二進制表示下不同位的個數。題目要求簡單直接：給定兩個整數 x 和 y，計算并返回它們之間的漢明距離。

一、問題解析

漢明距離的定義為兩個等長字符串對應位置不同字符的個數。在本題中，我們將其應用于整數的二進制表示。例如，對于 x = 1（二進制 0001）和 y = 4（二進制 0100），它們在第一和第三位不同，因此漢明距離為 2。

二、解決方案

以下是幾種常見的解法，從暴力到優化，逐步深入。

方法一：逐位比較法

最直觀的方法是逐位比較 x 和 y 的二進制位。我們可以通過循環 32 次（假設為 32 位整數），每次檢查最低位是否相同，然后右移一位。

步驟：

1. 初始化計數器 count = 0。
2. 循環 32 次，每次比較 x 和 y 的最低位（通過 x & 1 和 y & 1 獲取）。
3. 如果不同，count 加 1。
4. 將 x 和 y 右移一位（x >>= 1, y >>= 1）。
5. 返回 count。

時間復雜度：O(1)，因為固定循環 32 次。
空間復雜度：O(1)。

方法二：異或運算優化

利用位運算中的異或（XOR）操作，可以更高效地解決問題。異或運算的規則是：相同為 0，不同為 1。因此，將 x 和 y 進行異或后，結果中 1 的個數即為漢明距離。

步驟：

1. 計算 z = x ^ y。
2. 統計 z 中 1 的個數。統計方法有多種：

• 循環計數法：類似方法一，循環檢查 z 的最低位是否為 1，然后右移。

• Brian Kernighan 算法：這是一種高效算法，通過 z & (z - 1) 不斷清除最低位的 1，直到 z 變為 0。每次操作計數器加 1。

時間復雜度：O(1)，因為整數位數固定。
空間復雜度：O(1)。

方法三：內置函數法

許多編程語言提供了內置函數來統計二進制中 1 的個數（例如 Java 的 Integer.bitCount() 或 Python 的 bin().count('1')）。這種方法代碼簡潔，但底層實現通常基于高效算法。

三、代碼示例（Python）

以下是方法二的 Python 實現，使用 Brian Kernighan 算法：

def hammingDistance(x: int, y: int) -> int:
z = x ^ y
count = 0
while z:
z &= z - 1  # 清除最低位的 1
count += 1
return count

四、應用場景

漢明距離在計算機科學中有廣泛的應用，例如：

• 錯誤檢測與糾正：在網絡傳輸或存儲系統中，用于衡量數據差異。
• 信息檢索：在相似性搜索中，比較二進制特征向量。
• 密碼學：評估密鑰或哈希值的差異。

五、

LeetCode 461 題通過位運算的核心技巧，幫助開發者熟悉異或操作和二進制處理。掌握此類問題不僅能提升算法能力，還能加深對計算機底層原理的理解。建議在解題時優先考慮異或結合 Brian Kernighan 算法，以實現高效且簡潔的解決方案。