LeetCode 461. Hamming Distance

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 461. Hamming Distance 原题链接简单

作者：

wzc1995 , 2018-06-30 16:43:50 , 所有人可见 , 阅读 1261

题目描述

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

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

说明

0 <= x, y < 2^31

样例

输入：x = 1, y = 4

输出：2

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

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

算法

(位运算) $O(\log x)$

令 z 等于 x ^ y ，然后只需要统计 z 的数位上有多少个 1。

时间复杂度

异或的时间复杂度为 $O(1)$，统计二进制位 1 的个数时间复杂度为 $O(\log x)$，故总时间复杂度为 $O(\log x)$。

空间复杂度

仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int hammingDistance(int x, int y) {
        int z = x ^ y, ans = 0;
        for(; z; z -= z & -z)
            ans++;

        return ans;
    }
};

4 评论

simonhan 2021-05-27 13:15

### go

func hammingDistance(x int, y int) int {
    ans, s := 0, x^y
    for s != 0 {
        s -= (s & (-s))
        ans++
    }
    return ans
}

### rust

impl Solution {
    pub fn hamming_distance(x: i32, y: i32) -> i32 {
        let (mut ans,mut s) = (0,x ^y);
        while s != 0{
            s -= (s & (-s));
            ans += 1;
        }
        return ans;
    }
}