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 < 2^31.

海明距离，我想到的办法就是最笨也就是简单的办法，就是用两个数组来存储x,y对应的二进制序列，之后再对数组遍历比较不同的位数，从而得到答案。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int bitsOfA[32];
        int bitsOfB[32];
        for (int i = 0; i < 32; ++i) {
            bitsOfA[i] = 0;
            bitsOfB[i] = 0;
        }
        int j = 0;
        //x十进制转化为二进制，倒序
        while (x > 0) {
            bitsOfA[j++] = x % 2;
            x = x / 2;
        }
        j = 0;
        //x十进制转化为二进制，倒序
        while (y > 0) {
            bitsOfB[j++] = y % 2;
            y = y / 2;
        }
        //遍历寻找不同位数，得到答案
        int number = 0;
        for (int k = 0; k < 32; ++k) {
            if (bitsOfA[k] != bitsOfB[k]) {
                number++;
            }
        }
        return number;
    }
};

然而，这道题使用位运算会更加简便。因为是寻找二进制不同位数，所以只需要数数n=x^y得到的二进制数上有多少个1即为答案。

再计算n的二进制上1的个数用的是一个循环，当n不为0时循环，重点在 n &= n - 1，执行这个“与”运算后会把n对应的二进制最右边的1转化为0。每转化一次dist++，当所有的1都转化为0后dist就为最终答案。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int dist = 0, n = x ^ y;
        while (n) {
            ++dist;
            n &= n - 1;
        }
        return dist;
    }
};