位1的个数 - Githubissues

题目

示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：

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

在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

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

解答

核心目的：求出给定数的二进制表达式中'1'的个数。

方法一：移位取末尾

通过不断取二进制最后一位，并且每取一次，二进制数右移一位。累加最后一位。

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >> = 1;
    }
    return count;
}

n & 1：由于1的二进制表达式只有最后一位为1，因此任何数对1进行&运算，均是取该数二进制的最后一位。
循环条件n != 0：最开始我使用的是循环32次，但是实际上大部分情况都不需要把所有位都统计一遍，因为当数为0时，二进制表达式中就不存在有1的数位了。

方法二：分治法（骚操作）

源自：位运算简介及实用技巧（二）：进阶篇(1)

首先给出一个二进制数：1011_0111。

如何计算它二进制表达式中1的个数呢？

解析

参考归并排序，我们将问题细化：目的是上述二进制（8位）中1的个数，那么也就是求高 4 位和低 4 位中1的和，也就等于求1~2、3~4、5~6、7~8位中1的个数，即单个数位上1的个数之和 => 目前数二进制的状态。

那么现在就是合并单个数位上的结果，将上述流程反向操作，合并结果。

:warning:：注意下文中表达式若无特别说明均为二进制。

第一步：参考归并排序，将二进制数看做一个数组，相邻两位作为一个分组：

10|11|01|11

第二步：统计分组中1的个数

单独看最低位的那个二进制分组（11）：

低位上1的个数：11 & 0x01 = 01
高位上1的个数：(11 >> 1) & 01 = 01

然后对结果进行求和即为该分组中1的个数：01 + 01 = 10 = 2（十进制）

推导到示例中：

低位分组：1011_0111 & 0101_0101 = 0001_0101
高位分组：(1011_0111 >> 1) & 0101_0101 = 0101_0001
求和：0001_0101 + 0101_0001 = 0110_0110

📝：0101_0101的16进制表达形式为0x55

⚠️验证方式：这一步的求和结果需要单独根据分组验证，如下

最低位10：代表此分组包含 2 个（1）
次低位01：分组包含 1 个
次高位10：分组包含 2 个
最高位01：分组包含 1 个

第三步：重复第一步，将分组扩大为 4 位

0110|0110

第四步：重复第二步，求得分组的和

低位：0110_0110 & 0011_0011 = 0010_0010
高位：(0110_0110 >> 2) & 0011_0011 = 0001_0001
求和：0001_0001 + 0010_0010 = 0011_0011

📝：0011_0011的16进制表达形式为0x33

后续略...

直至分组大小为 16 ，再进行最后一次求和即可得到结果。

代码

public int hammingWeight(int n) {
    n = (n & 0x5555_5555) + ((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;
}

优点：平均效率要优于上一种解法

缺点：代码可读性低

xiwenAndlejian / my-blog

位1的个数 #26

题目

解答

方法一：移位取末尾

方法二：分治法（骚操作）

解析

代码