461. 汉明距离

链接: 461. 汉明距离

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

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

题解

朴素版本

模拟判断每一位, !=号, 可以使用^代替

class Solution {
public:
    int hammingDistance(int x, int y) {
        int res = 0;
        while (x || y) {
            if ((x & 1) ^ (y & 1))
                ++res;
            x >>= 1;
            y >>= 1;
        }
        return res;
    }
};

C++

朴素版本的优化版: $Brian Kernighan$ 算法

因为^就是使得不同的位变为1的, 而相同的位就会变为0, 故此直接统计即可.

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

C++

库函数

直接就是 $O(1)$ 的, 具体见2595. 奇偶位数/191. 位1的个数有推导

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

C++