HammingDistance [source code]

public class HammingDistance {
    public int hammingDistance(int x, int y) {
        int xorResult = x ^ y;
        int count = 0;
        while (xorResult > 0) {
            xorResult &= (xorResult - 1);
            count ++;
        }
        return count;
    }
}

这个问题的最优解是直接:
return Integer.bitCount(x ^ y);

当然,这个就有点没意思了, 这里重要的还是学习bit manipulation的技巧;

总体思路是类似的, 先把x and y一个 xor, 把问题转换成为count bit 1 in this number;

这里这个 whileloop 其实是有点难以理解的, 这里的一个key fact 是, x &= (x-1) 这个操作完成的操作就是turn the rightmost bit 1 in x to bit 0;

具体的证明可以假设个位分别是0和1:
如果是1, 很好证明, 个位上的1被消除了;
如果是0, 那么在 x 的右边肯定有一个类似10..0这样的 pattern, 这样一个 pattern 也是 -1的时候承受负担的pattern, 会被变成01..1, 然后整个都被消除, 实际最后达到的效果就是10..0的1被消除了, 也就是rightmost bit 1被消除了;

当然这个底层具体的原理我现在还是不是很清楚, 后面如果有时间看看hacker's delight看看上面有没有讲这个的东西. 只能说这些技巧暂时一边做一边记好了.

记忆这个算法的作用应该是, 比如可以用来turn bit 1 to bit 0 from right to left, one by one;

这里是另外一个解法:

public int hammingDistance(int x, int y) {  
    int xor = x ^ y, count = 0;  
    for (int i=0;i<32;i++) count += (xor >> i) & 1;  
    return count;  
}

或者用一个稍微优化了一下之后的版本:

public int hammingDistance(int x, int y) {  
    int xor = x^y;  
    int res = 0;  
    while(xor!=0) {  
        res+= xor & 1;  
        xor >>= 1;  
    }  
    return res;  
}

这个算法就相对更有指导意义, 算法本身的内核没有前面的那个那么sleek.
这个算法的想法也很简单, 这个问题就是count 1嘛, 所以我们从右到左, 每一个 iteration 数一个1, 数的位置在个位, 数的方式是判断个位是否是1(具体写起来, 使用的 & 1);这个算法的指导意义在于给出了一个比较好用的遍历一个数的 bits 的思路;

Problem Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

Bit Manipulation
Hide Similar Problems (E) Number of 1 Bits (M) Total Hamming Distance