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

一、問題解析

漢明距離的定義為兩個(gè)等長(zhǎng)字符串對(duì)應(yīng)位置不同字符的個(gè)數(shù)。在本題中，我們將其應(yīng)用于整數(shù)的二進(jìn)制表示。例如，對(duì)于 x = 1（二進(jìn)制 0001）和 y = 4（二進(jìn)制 0100），它們?cè)诘谝缓偷谌徊煌虼藵h明距離為 2。

二、解決方案

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

方法一：逐位比較法

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

步驟：

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

時(shí)間復(fù)雜度：O(1)，因?yàn)楣潭ㄑh(huán) 32 次。
空間復(fù)雜度：O(1)。

方法二：異或運(yùn)算優(yōu)化

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

步驟：

1. 計(jì)算 z = x ^ y。
2. 統(tǒng)計(jì) z 中 1 的個(gè)數(shù)。統(tǒng)計(jì)方法有多種：

• 循環(huán)計(jì)數(shù)法：類似方法一，循環(huán)檢查 z 的最低位是否為 1，然后右移。

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

時(shí)間復(fù)雜度：O(1)，因?yàn)檎麛?shù)位數(shù)固定。
空間復(fù)雜度：O(1)。

方法三：內(nèi)置函數(shù)法

許多編程語言提供了內(nèi)置函數(shù)來統(tǒng)計(jì)二進(jìn)制中 1 的個(gè)數(shù)（例如 Java 的 Integer.bitCount() 或 Python 的 bin().count('1')）。這種方法代碼簡(jiǎn)潔，但底層實(shí)現(xiàn)通常基于高效算法。

三、代碼示例（Python）

以下是方法二的 Python 實(shí)現(xiàn)，使用 Brian Kernighan 算法：

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

四、應(yīng)用場(chǎng)景

漢明距離在計(jì)算機(jī)科學(xué)中有廣泛的應(yīng)用，例如：

• 錯(cuò)誤檢測(cè)與糾正：在網(wǎng)絡(luò)傳輸或存儲(chǔ)系統(tǒng)中，用于衡量數(shù)據(jù)差異。
• 信息檢索：在相似性搜索中，比較二進(jìn)制特征向量。
• 密碼學(xué)：評(píng)估密鑰或哈希值的差異。

五、

LeetCode 461 題通過位運(yùn)算的核心技巧，幫助開發(fā)者熟悉異或操作和二進(jìn)制處理。掌握此類問題不僅能提升算法能力，還能加深對(duì)計(jì)算機(jī)底層原理的理解。建議在解題時(shí)優(yōu)先考慮異或結(jié)合 Brian Kernighan 算法，以實(shí)現(xiàn)高效且簡(jiǎn)潔的解決方案。