最近開始刷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.
我看到這道題，第一反應(yīng)就是先將兩個(gè)數(shù)轉(zhuǎn)換成二進(jìn)制，再逐位比較，這難道不是最直觀最明顯的解法嗎？那么我的思路就可以分為以下幾步：
1、獲取參數(shù)a的最末位，這可以用求余的辦法得到，a % 2；
2、接著我們需要獲取倒數(shù)第二位，這需要先將a右移一位 a >>> 1，然后再求余；
3、對(duì)b采用同樣的辦法，所以我們需要一個(gè)循環(huán)來比較a和b的各個(gè)位；
4、然而循環(huán)的終止條件怎么定？題設(shè)中給出了a和b都是正數(shù)，隨著二者的右移，肯定越來越小，所以終止條件就是較大的那個(gè)數(shù)右移之后等于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;    }}然后就在我洋洋得意的時(shí)候，看了一眼別人的代碼，被打臉了：
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;}
看到異或運(yùn)算的那一剎那我就傻眼了——有這么好用的辦法為啥我就沒想到呢？異或運(yùn)算之后，我們只要數(shù)一數(shù)結(jié)果里面有多少個(gè)1就行了，因?yàn)橹挥袃蓚€(gè)數(shù)相同位的值不同結(jié)果才是1，這就是核心思路。然后就是如何去數(shù)結(jié)果里面1的個(gè)數(shù)，上述答案使用了32次循環(huán)，每次循環(huán)內(nèi)比較xor的一個(gè)位和1的與運(yùn)算，如下：
1011 1001 1101
0000 0000 0001
因?yàn)?之前的位全是0，所以和xor對(duì)應(yīng)位的與運(yùn)算結(jié)果必是0；這樣xor和1的與運(yùn)算結(jié)果其實(shí)是xor的最后一位和1的與運(yùn)算結(jié)果，這辦法聰明！
要想知道xor倒數(shù)第二位是0還是1，需要將xor右移一位，再和1與運(yùn)算，這就是循環(huán)的道理。
不過這是有些浪費(fèi)的，因?yàn)閤or可能沒有那么大。
我改進(jìn)如下：
public int hammingDistance(int x, int y) {    int xor = x ^ y, count = 0;    while(xor > 0) {        count += xor & 1;        xor = xor >> 1;    }       return count;}
做一道題，真的學(xué)到不少東西。不如xor右移之后其實(shí)本身的值沒有改變，比如與運(yùn)算和異或運(yùn)算的妙用。現(xiàn)在反過來看我當(dāng)初的解法，真實(shí)圖樣圖森破，說到底還是見識(shí)不夠廣，積累不夠深，憑自己的那點(diǎn)小聰明遠(yuǎn)遠(yuǎn)不夠，成了一只坐井觀天的青蛙。
沒有天才，只有積累。