leetcode — 461. 漢明距離 Hamming Distance

兩個整數之間的 漢明距離 指的是這兩個數字對應二進制位不同的位置的數目。

給定兩個整數 

x

 和 

y

，計算并傳回它們之間的漢明距離。

示例 1：

輸入：x = 1, y = 4
輸出：2
解釋：
        1   (0 0 0 1)
        4   (0 1 0 0)
               ↑   ↑
        上面的箭頭指出了對應二進制位不同的位置。
      

示例 2：

輸入：x = 3, y = 1
輸出：1
      

提示：

• 0 <= x, y <= 2^31 - 1

• 資訊論中，Hamming Distance 表示兩個等長字元串在對應位置上不同字元的數目，以distance(x, y) 表示字元串x和y之間的 漢明距離。
• 漢明距離度量了通過替換字元的方式将字元串 x 變成 y 所需要的 最小的替換次數。

以下字元串之間的漢明距離：
    "karolin" and "kathrin" is 3.
    1011101 and 1001001 is 2.
    Liziyi and Lzziii is 2.
           

• 對于二進制串ａ和ｂ來說，漢明距離等于ａXOR(異或)ｂ中１的數目，又稱其為漢明權重。—— 相異為1，相同為0【同或（XNOR）】
• 長度為ｎ的二進制字元串通過漢明距離構成了一個度量空間(metric space)，稱其為漢明立方(Hamming Cube)。
• 大多數程式設計語言内置計算二進制表達中 1 的數量的函數。
  • C++ ： __builtin_popcount(x )
  • Java：Integer.bitCount(x)
  • Golang：bits.OnesCount(x)
  • C：__builtin_popcount(x)

        結合漢明距離的定義，對整體進行推導。

        兩個整數之間的漢明距離是 所對應位置上數字不同 的次數。使用異或（XOR，⊕），當且僅當對應位置數字不同時輸出為 1，相異為1，相同為0，可以對異或的結果中的 1 的個數進行統計，該結果表明 兩個整數之間 的 漢明距離。

9	1	1
12	1	1
9⊕12	1	1

        問題轉換為 一比特位計數 問題。 https://blog.csdn.net/qq_34176797/article/details/119035767

 方法一：使用語言中内置函數進行計算，先求兩個數字的異或結果，對結果中的 1 進行統計。

• 時間複雜度：O(1)。
• 空間複雜度：O(1)。

class Solution {
    public int hammingDistance(int x, int y) {
        // 求解 x 與 y 的異或結果
        return Integer.bitCount(x ^ y);
    }
}
           

方法二：移位 逐位判斷 統計異或之後二進制數中1的個數

算法流程：

• 初始化統計變量 count = 0。
• 循環逐位判斷， 當 n = 0 時結束循環。
  • count += n & 1 ： 若 n & 1 = 1 ，則統計數 res 加一。
  • num =  num >>  1 ： 将二進制數字 n 右移一位 。
•  傳回統計數量 count 。

class Solution {
    public int hammingDistance(int x, int y) {
        // 求解 x 與 y 的異或結果
        int num = x ^ y;

        // 逐位判斷，右移
        int count = 0;
        while(num != 0){
            count += num & 1;
            num >>= 1;
        }
        return count;
    }
}
           

 方法三：使用Brian Kernighan算法進行優化，跳過一些計算

        對任何一個數 n ，n & ( n − 1 ) 的結果是n 的比特位最右端的1變為0。

算法流程：

• 初始化統計變量 count = 0。
• 循環消除二進制數n最右邊的1， 當 n = 0 時結束循環。
  • count += 1 ；
  • num =  num & (num - 1) ：将n的比特位的最右端的1消除變為0。
•  傳回統計數量 count 。

class Solution {
    public int hammingDistance(int x, int y) {
        // 求解 x 與 y 的異或結果
        int num = x ^ y;

        // 每次将最右端的 1 消除
        int count = 0;
        while(num != 0){
            count += 1;
            num = num & (num - 1);
        }
        return count;
    }
}