461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：

0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4
输出: 2

解释:

1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

思路：

x和y按位异或，得到所有不同的位
模二取余，余数累加

具体代码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int z = x ^ y; //按位异或
        int res = 0;   //结果
        while(z){ //遍历z每一位
            if(z % 2){ //假设z最低位为1
                res++; //结果++
            }
            z /= 2;  //z抹去最后一位
        }
        return res; //返回结果
    }
};

代码借鉴：

百度发现了一个新颖的写法
参考资料《leetCode:461 汉明距离》

class Solution {
    public int hammingDistance(int x, int y) {
        int sum = x ^ y;
        int count;
        for(count = 0; sum > 0; count++){
            sum &= (sum - 1);
        }
        return count;
    }
}

其中关键一句是 sum &= (sum - 1)
这句话的作用是，删除sum从右起第一个1
证明：
加入sum形如xxxx1,
则sum - 1形如xxxx0
做与运算后，结果为xxxx0，末尾的1被删去了

假设sum形如xxxx100...00
则sum - 1形如xxxx011...11
做与运算后，结果为xxxx000...00，可以观察到，末尾的1被删去了

这个方法执行for循环，效果也很不错，也不用添加额外的if判断了