天天看點

461. 漢明距離 461. 漢明距離

461. 漢明距離

1. 題目

題目連結

461. 漢明距離 461. 漢明距離

2. 題目分析

計算兩個數字對應二進制位不同的位置的數目,這題比較簡單,正常的思維的是,将兩個數字先轉化成二進制,然後逐一比較統計不同的二進制位數。這種方法的時間複雜度log2X + log2Y + n;

另一種方法:先求x和y異或運算的值xor,然後求出xor的二進制中的1的個數,即是x和y的二進制不同的數的個數,這個方法的時間複雜度是主要在計算xor的二進制的1的個數中,通過n = n & n-1 計算,可以減小到M,即二進制中M個1。

3. 解題思路

4. 代碼實作(java)

class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int count = countBanaryNum(xor);
        return count;
    }

    /**
     * 計算二進制中1的個數
     * @return
     */
    public static int countBanaryNum(int n){
        int count = 0;
        while (n != 0){
            n = (n & (n-1));
            count++;
        }
        return count;
    }
}