统计二进制中 1 的个数的几种方式

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

题目描述

这是 LeetCode 上的 191. 位1的个数 。

Tag : 「位运算」

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
复制代码

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
复制代码

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
复制代码

提示：

输入必须是长度为 32 的二进制串。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

「位数检查」解法

一个朴素的做法是，对 int 的每一位进行检查，并统计 1 的个数

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans += ((n >> i) & 1);
        }
        return ans;
    }
}
复制代码

时间复杂度： $O(k)$ ，k 为 int 的位数，固定为 32 位
空间复杂度： $O(1)$

「右移统计」解法

对于方法一，即使 n 的高位都是 0，我们也会对此进行循环检查。

因此另外一个做法是：通过 $n & 1$ 来统计当前 $n$ 的最低位是否为 1，同时每次直接对 $n$ 进行右移并高位补 0。

当 $n = 0$ 代表，我们已经将所有的 1 统计完成。

这样的做法，可以确保只会循环到最高位的 1 。

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            ans += (n & 1);
            n >>>= 1;
        }
        return ans;
    }
}
复制代码

时间复杂度： $O(k)$ ，k 为 int 的位数，固定为 32 位，最坏情况 $n$ 的二进制表示全是 1
空间复杂度： $O(1)$

「分组统计」解法

以上两种解法都是 $O(k)$ 的，事实上我们可以通过分组统计的方式，做到比 $O(k)$ 更低的复杂度。

public class Solution {
    public int hammingWeight(int n) {
        n = (n & 0x55555555) + ((n >>> 1)  & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2)  & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >>> 4)  & 0x0f0f0f0f);
        n = (n & 0x00ff00ff) + ((n >>> 8)  & 0x00ff00ff);
        n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
        return n;
    }
}
复制代码

时间复杂度： $O(\log{k})$ ，k 为 int 的位数，固定为 32 位
空间复杂度： $O(1)$

PS. 对于该解法，如果大家学有余力的话，还是建议大家在纸上模拟一下这个过程。如果不想深入，也可以当成模板背过（写法非常固定），但通常如果不是写底层框架，你几乎不会遇到需要一个 $O(\log{k})$ 解法的情况。而且这个做法的最大作用，不是处理 int，而是处理更大位数的情况，在长度只有 32 位的 int 的情况下，该做法不一定就比循环要快（该做法会产生多个的中间结果，导致赋值发生多次，而且由于指令之间存在对 n 数值依赖，可能不会被优化为并行指令），这个道理和对于排序元素少的情况下，我们会选择「冒泡排序」而不是「归并排序」是一样的，因为「冒泡排序」常数更小。