题目

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

https://leetcode.cn/problems/number-of-1-bits/description/

‍

解法一：右移统计

解题思路

右移统计，判断最后一位是否为 1。

1. 只要 n != 0，我们就可以知道 n 的二进制表示当中肯定包含有 1，不管它在哪个位置。

2. 只要 n & 1 = 1，我们就可以知道 n 的最后一位肯定是1。

3. 那么根据前两个条件，我们可以把 n 不断的向右移 1 位，高位补0, 然后不断累加记录最后一位是 1 的次数，直到移动到 n = 0 结束。

代码实现

public class Solution {    public int hammingWeight(int n) {        int cnt = 0;        while(n != 0){            if((n & 1) == 1){                cnt++;            }            // 逻辑右移动，高位补0；            // 这里不能使用算术右移，因为算术右移会在高位补符号位，            // 如果是负数，那么高位会补1，这样会导致while循环一直出不去。            n = n >>> 1;        }        return cnt;    }}

复杂度分析

时间复杂度 O(logN)：时间复杂度为while循环的次数，取决于 n 的二进制表示中最高位的 1 在哪个位置，即以2为底的log(n)向下取整 + 1，最坏的情况下就是32次。

空间复杂度 O(1)：只开了一个变量cnt用于存放结果，空间复杂度为1。

解法二：清除最低位

解题思路

使用最低位的思路，n = n & (n - 1) 表示删掉 n 的最低位。

1. 只要 n != 0, 表示 n 的二进制表示中包含有 1，计数加一。

2. 删掉 n 的最低位，判断是否还满足 n != 0，满足则计数加一并继续删掉最低位；不满足则结束。

代码实现

public class Solution {
    public int hammingWeight(int n) {        int cnt = 0;        while(n != 0){            cnt++;            n = n & (n - 1);        }                return cnt;    }}

复杂度分析

空间复杂度 O(1)：只开了一个变量cnt用于存放结果，空间复杂度为1。

解法三：分治

解题思路

利用分治的思想，将每个位置的1加起来即可，以181=1011 0101为例：

1. 两两一组相加，将8位二进制会分为4组（如果是32位，那么就会分成16组）。相加后二进制表达为 01_10_01_01，代表的是4组结果：1 + 2 + 1 + 1 = 5。

2. 将第一步得到的4组结果再进行两两一组相加，结果为0011_0010, 代表 3 + 2 = 5。

3. 将第二步得到的2组结果合并相加，结果为00000101=5。

注意：直到最后一步的时候，所有的二进制位都合并为一组的时候，其结果才是一个真正的数值，前面所有步骤中的结果只在分组中是有效数值。32位计数同理。

算法图解：

思路有了，那么接下来分析如何让两两一组相加呢？

1. 我们可以新开一个数，使其二进制表达为原数值的二进制向后移动一位，首位补0，这样就刚好让分在同一组的两个位置对其。

2. 对齐后我们需要两个数相加，我们需要将原数值中绿色部分和新数值的蓝色部分清空（重复冗余数据），清空方式为 &01010101, 16进制表达为 &0x55。

3. 相加结果为01_10_01_01，与上述解题思路得到一致的结果。

4. 将第三步得到的结果再分组相加，逻辑同上。但是这个时候每个分组中有2个位置，所有删除冗余数据的时候需要 &00110011 = &0x33。

5. 循环上述步骤，直到所有二进制位都被分到同一组为答案。

代码实现

public class Solution {   public int hammingWeight(int n) {    // 每组1个位置，右移1位对齐并删除冗余数据（&01010101）。        n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);        // 每组2个位置，右移2位对齐并删除冗余数据（&00110011）。        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);        // 每组4个位置，右移4位对齐并删除冗余数据（&00001111）。        n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);        // 每组8个位置，右移8位对齐并删除冗余数据（&0000000011111111）。        n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);        // 每组16个位置，右移16位对齐并删除冗余数据（&000000000000000001111111111111111）。        n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
        // 最后32位二进制全部合并到一组，即为答案。        return n;    }}

复杂度分析

空间复杂度 O(1)

解法四：JDK Integer.bitCount(int i)

解题思路

解法4是解法3的优化。

1. n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);

•   0b11: 0b01 + 0b01 = 0b10 2个

•   0b10: 0b00 + 0b01 = 0b01 1个

•   0b01: 0b01 + 0b00 = 0b01 1个

•   0b00: 0b00 + 0b00 = 0b00 0个

两两一组相加时有上述4种情况，从中我们可以发现：

•   0b10 = 0b11 - 0b01

•   0b01 = 0b10 - 0b01

•   0b01 = 0b01 - 0b00

•   0b00 = 0b00 - 0b00

即计算后的结果 n = n - ((n >>> 1) & 0x55555555) = (n & 0x55555555) + ((n >>> 1) & 0x55555555)，优化后少了一次&运算。

我们可以验证一下1101（3个1）：

优化前：(n & 0x55555555) + ((n >>> 1) & 0x55555555) = 0b01_01 + ((0b01_10) & 0x5) = 0b01_01 + 0b01_00 = 0b10_01 = 2 + 1 = 3。

优化后：n - ((n >>> 1) & 0x5) = 0b11_01 - ((0b01_10) & 0x5) = 0b11_01 - 0b_0100 = 0b10_01 = 2 + 1 = 3。

2. n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);

无优化

3. n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);

这个优化方式是这样考虑的，因为这里刚好是8个位置为一组，也就是一个字节，最多有8个1，二进制表达最大为0000_1000，有后面4位就已经够用了，所以可以先用(n + (n >>> 4))把后面4位算出来，再&0f0f将前4位清空，优化为：n = (n + (n >>> 4)) & 0x0f0f0f0f，少了一次&运算。

4. n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);

同方法3一样，这里是16位为一组，最多16个1，二进制表达最大为0000_0000_0001_0000，前8位全是0，可以暂时忽略，可以先用后8位相加，然后再清空前8位。

优化为：n = (n + (n >>> 8)) & 0x00ff00ff。

5. n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);

同上，优化为：n = (n + (n >>> 16)) & 0x0000ffff。

6. 进一步观察，会发现，第4步第5步的有效位都在最后的8位上，前面的都是无效位，所以可以将清空操作放到最后，只保留最后8位有效位置，前面的全部清空，即 &0b1111_111111 = &0xff。

再进一步观察，第4步有效位是最后5位，第5步有效位是最后6位（0b10_0000 = 32），第7位第8位肯定全部为0，所以也可以&0b11_111111 = &0x3f。

代码实现

public class Solution {   public int hammingWeight(int n) {    n = n - ((n >>> 1) & 0x55555555);        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);        n = (n + (n >>> 4)) & 0x0f0f0f0f;        n = n + (n >>> 8);        n = n + (n >>> 16);        return n & 0x3f;    }}

复杂度同解法三。

本篇文章来源于微信公众号: i余数