2021-1-30 461. 汉明距离

个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 2^31.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hamming-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

class Solution {
public:
    vector<int> binary(int x){
        vector<int> nums;
        while(x!=0){
            int num=x%2;
            x=x/2;
            nums.push_back(num);
        }
        return nums;
    }
    int hammingDistance(int x, int y) {
        int diff=0;
        if(x>=y){
            swap(x,y);
        }
        vector<int> xbinary=binary(x);
        vector<int> ybinary=binary(y);
        int count=ybinary.size()-xbinary.size();
        for(int i=0;i<count;i++){
            xbinary.push_back(0);
        }
        int size=xbinary.size();
        for(int i=0;i<size;i++){
            if(xbinary[i]!=ybinary[i]){
                diff++;
            }
        }
        return diff;

    }
};

官方题解：

方法一 按位异或，之后输出1的数目
class Solution {
public:
    int hammingDistance(int x, int y) {
        return bitset<32> (x ^ y).count();
    }
};

作者：OrangeMan
链接：https://leetcode-cn.com/problems/hamming-distance/solution/cjian-jie-dai-ma-shuang-bai-1xing-by-orangeman/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二 按位异或，移位
方法三 布赖恩·克尼根算法
class Solution {
public:
    int hammingDistance(int x, int y) {
    int  n = x ^ y, count = 0;
    while(n)
    {
        n &= n-1;
        count++;
    }
    return count;
    }
};

作者：zrita
链接：https://leetcode-cn.com/problems/hamming-distance/solution/c-z-by-zrita-12/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

注：
① C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。
② 计算异或之后数组中1的数目，可以通过n=n&（n-1）来操作，每次消除最末尾的一个1，记录消除的总数就好.