leetcode 461.漢明距離 - 位運算

題幹

兩個整數之間的漢明距離指的是這兩個數字對應二進制位不同的位置的數目。

給出兩個整數 x 和 y，計算它們之間的漢明距離。

注意：

0 ≤ x, y < 231.

示例:

輸入: x = 1, y = 4

輸出: 2

解釋:

1 (0 0 0 1)

4 (0 1 0 0)

↑ ↑

上面的箭頭指出了對應二進制位不同的位置。

知識點&算法

題解

先統計兩個數從低到高相異的位數，然後統計剩下的1。

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;
        }           
        if(x) res += __builtin_popcount(x);
        else if(y) res += __builtin_popcount(y);
        return res;
    }
};
           

還就那個多此一舉，直接利用異或的特性，同0異1，先異或再統計1的個數

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

也可以寫成

Brian Kernighan 算法：

一個數-1的結果相當于将原數最低位的1置0，其右側0全置1。是以一個數和其-1的結果做與運算，就可以将原數最低位的1置0。

通過這種方法來統計二進制1的個數。

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