LeetCode之Hamming Distance

最近开始刷LeetCode，先从简单的开始吧。

461. Hamming Distance

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 = 4Output: 2Explanation:1   (0 0 0 1)4   (0 1 0 0)       ↑   ↑The above arrows point to positions where the corresponding bits are different.
我看到这道题，第一反应就是先将两个数转换成二进制，再逐位比较，这难道不是最直观最明显的解法吗？那么我的思路就可以分为以下几步：
1、获取参数a的最末位，这可以用求余的办法得到，a % 2；
2、接着我们需要获取倒数第二位，这需要先将a右移一位 a >>> 1，然后再求余；
3、对b采用同样的办法，所以我们需要一个循环来比较a和b的各个位；
4、然而循环的终止条件怎么定？题设中给出了a和b都是正数，随着二者的右移，肯定越来越小，所以终止条件就是较大的那个数右移之后等于0；
看我代码：
public class Solution {    public int hammingDistance(int x, int y) {        int res = 0;        int max = x > y ? x : y;        int min = x <= y ? x : y;                while(max > 0) {            if(max % 2 != min % 2)                res++;                            max = max >>> 1;            min = min >>> 1;        }                return res;    }}然后就在我洋洋得意的时候，看了一眼别人的代码，被打脸了：
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;}
看到异或运算的那一刹那我就傻眼了——有这么好用的办法为啥我就没想到呢？异或运算之后，我们只要数一数结果里面有多少个1就行了，因为只有两个数相同位的值不同结果才是1，这就是核心思路。然后就是如何去数结果里面1的个数，上述答案使用了32次循环，每次循环内比较xor的一个位和1的与运算，如下：
1011 1001 1101
0000 0000 0001
因为1之前的位全是0，所以和xor对应位的与运算结果必是0；这样xor和1的与运算结果其实是xor的最后一位和1的与运算结果，这办法聪明！
要想知道xor倒数第二位是0还是1，需要将xor右移一位，再和1与运算，这就是循环的道理。
不过这是有些浪费的，因为xor可能没有那么大。
我改进如下：
public int hammingDistance(int x, int y) {    int xor = x ^ y, count = 0;    while(xor > 0) {        count += xor & 1;        xor = xor >> 1;    }       return count;}
做一道题，真的学到不少东西。不如xor右移之后其实本身的值没有改变，比如与运算和异或运算的妙用。现在反过来看我当初的解法，真实图样图森破，说到底还是见识不够广，积累不够深，凭自己的那点小聪明远远不够，成了一只坐井观天的青蛙。
没有天才，只有积累。