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