461. 漢明距離

1. 題目

題目連結

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;
    }
}