[LeetCode]461. Hamming Distance

发表于 | 分类于 | 评论数： | 阅读次数：
字数统计：331 字 | 阅读时长：2 分钟

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:

1
2
3
4
5
6
7
8
9
10
Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

题目解释：两个整数，计算转换成二进制后，同一个位置上，两个数不同的有几个。

思路：算出所有不同的位置，直接用异或，再去统计所有异或出来的‘1’的个数。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingDistance(int x, int y) {
        int n = x^y;
        unsigned int c =0;
        for (c =0; n; n >>=1) {
             c += n & 1;
        } 
        return c;
    }
};

result

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Hamming Distance.

Memory Usage: 8.2 MB, less than 73.49% of C++ online submissions for Hamming Distance.

逛了一遍讨论区，各种奇技淫巧，效果并没有更好，找不到内存占用小于8.2MB的办法，如果有谁找到了，麻烦留言告知。

1
2
3
4
5
6
class Solution {
public:
    int hammingDistance(int x, int y) {
        return bitset<32>(x^y).count();
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingDistance(int x, int y) {
        int dist = 0, n = x ^ y;
        while (n) {
            ++dist;
            n &= n - 1;
        }
        return dist;
    }
};
1
2
3
4
5
6
class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);
    }
};