leetcode-461-汉明距离

汉明距离

题面

leetcode题目

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

给出两个整数 x 和 y，计算它们之间的汉明距离。 注意： \(0 \leq x, y\eq 2^31\)

example

输入: x = 1, y = 4

输出: 2

解释

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

题解

总体思路

二进制不同的位置类比于异或啦，\(a\oplus b = x\)的结果\(x\)表示\(a\)和\(b\)中二进制位不同时为1，此时再统计结果\(x\)中的二进制位为1的次数即可。 统计二进制位为1的次数也是有套路的，有一个trick的写法。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

#define _NDEBUG

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