位1的个数

[xiwenAndlejian]

191. 位1的个数

题目

• 示例 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的个数之和 => 目前数二进制的状态。

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

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

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

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;
}

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

缺点：代码可读性低