LC 461. 汉明距离

题目描述

这是 LeetCode 上的 461. 汉明距离 ，难度为 简单。

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

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

示例:

输入: x = 1, y = 4

输出: 2

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

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

提示：

• $0 <= x, y <= 2^{31} - 1$

---

逐位比较

本身不改变 $x$ 和 $y$，每次取不同的偏移位进行比较，不同则加一。

循环固定取满 $32$ 。

Java 代码：

class Solution {
    public int hammingDistance(int x, int y) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int a = (x >> i) & 1 , b = (y >> i) & 1;
            ans += a != b ? 1 : 0;
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int a = (x >> i) & 1, b = (y >> i) & 1;
            ans += a != b ? 1 : 0;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        ans = 0
        for i in range(32):
            a, b = (x >> i) & 1, (y >> i) & 1
            ans += a != b
        return ans

TypeScript 代码：

function hammingDistance(x: number, y: number): number {
    let ans = 0;
    for (let i = 0; i < 32; i++) {
        let a = (x >> i) & 1, b = (y >> i) & 1;
        ans += a !== b ? 1 : 0;
    }
    return ans;
};

• 时间复杂度：$O(C)$，$C$ 固定为 $32$
• 空间复杂度：$O(1)$

---

右移统计

每次都统计当前 $x$ 和 $y$ 的最后一位，统计完则将 $x$ 和 $y$ 右移一位。

当 $x$ 和 $y$ 的最高一位 $1$ 都被统计过之后，循环结束。

Java 代码：

class Solution {
    public int hammingDistance(int x, int y) {
        int ans = 0;
        while ((x | y) != 0) {
            int a = x & 1, b = y & 1;
            ans += a ^ b;
            x >>= 1; y >>= 1;
        }
        return ans;
    }
}

C++ 代码：

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

Python 代码：

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        ans = 0
        while (x | y) != 0:
            a, b = x & 1, y & 1
            ans += a ^ b
            x, y = x >> 1, y >> 1
        return ans

TypeScript 代码：

function hammingDistance(x: number, y: number): number {
    let ans = 0;
    while ((x | y) !== 0) {
        let a = x & 1; let b = y & 1;
        ans += a ^ b;
        x >>= 1; y >>= 1;
    }
    return ans;
};

• 时间复杂度：$O(C)$，$C$ 最多为 $32$
• 空间复杂度：$O(1)$

---

lowbit

熟悉树状数组的同学都知道，lowbit 可以快速求得 $x$ 二进制表示中最低位 $1$ 表示的值。

因此我们可以先将 $x$ 和 $y$ 进行异或，再统计异或结果中 $1$ 的个数。

Java 代码：

class Solution {
    int lowbit(int x) {
        return x & -x;
    }
    public int hammingDistance(int x, int y) {
        int ans = 0;
        for (int i = x ^ y; i > 0; i -= lowbit(i)) ans++;
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int lowbit(int x) {
        return x & -x;
    }
    int hammingDistance(int x, int y) {
        int ans = 0;
        for (int i = x ^ y; i > 0; i -= lowbit(i)) ans++;
        return ans;
    }
};

Python 代码：

class Solution:
    def lowbit(self, x):
        return x & -x
    def hammingDistance(self, x: int, y: int) -> int:
        ans, cur = 0, x ^ y
        while cur > 0:
            ans += 1
            cur -= self.lowbit(cur)
        return ans

TypeScript 代码：

function lowbit(x: number): number {
    return x & -x;
}
function hammingDistance(x: number, y: number): number {
    let ans = 0;
    for (let i = x ^ y; i > 0; i -= lowbit(i)) ans++;
    return ans;
};

• 时间复杂度：$O(C)$，$C$ 最多为 $32$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.461 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。