统计两数「二进制表示中不同位」个数的几种方式 | Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

逐位比较

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

循环固定取满 $32$ 。

代码：

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;
    }
}
复制代码

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

右移统计

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

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

代码：

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;
    }
}
复制代码

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

lowbit

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

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

代码：

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;
    }
}
复制代码

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