1. 位1的个数

川长思鸟来 2024-03-30 11:15 66阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法一：右移统计
     *   *  解题思路
         *  代码实现
         *  复杂度分析
     *  解法二：清除最低位
     *   *  解题思路
         *  代码实现
         *  复杂度分析
     *  解法三：分治
     *   *  解题思路
         *  代码实现
         *  复杂度分析
     *  解法四：JDK Integer.bitCount(int i)
     *   *  代码实现

### 题目 ###

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

### 解法一：右移统计 ###

#### 解题思路 ####

右移统计，判断最后一位是否为 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 ( l o g N ) O(logN) O(logN)**：时间复杂度为while循环的次数，取决于 n 的二进制表示中最高位的 1 在哪个位置，即以2为底的log(n)向下取整 + 1，最坏的情况下就是32次。

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

### 解法二：清除最低位 ###

#### 解题思路 ####

使用最低位的思路，n = n & (n - 1) 表示删掉 n 的最低位，参见[算法题中常用的位运算][Link 1]。

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 ( M ) O(M) O(M)**：时间复杂度M为二进制表示中 1 的个数，M <= log(n) + 1。当最高位是1，其他位都是0的时候，解法一需要32次，解法二只需要1次。

**空间复杂度  O ( 1 ) O(1) 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的个数][1]

**算法图解：**  
思路有了，那么接下来分析如何让两两一组相加呢？

1.  我们可以新开一个数，使其二进制表达为原数值的二进制向后移动一位，首位补0，这样就刚好让分在同一组的两个位置对其。
2.  对齐后我们需要两个数相加，我们需要将原数值中绿色部分和新数值的蓝色部分清空（重复冗余数据），清空方式为 &01010101, 16进制表达为 &0x55。
3.  相加结果为01\_10\_01\_01，与上述解题思路得到一致的结果。

![位1的个数-分治算法][1_-]

1.  将第三步得到的结果再分组相加，逻辑同上。但是这个时候每个分组中有2个位置，所有删除冗余数据的时候需要 &00110011 = &0x33。  
    ![位1的个数-分治算法][1_- 1]
2.  循环上述步骤，直到所有二进制位都被分到同一组为答案。

#### 代码实现 ####

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 ( l o g N ) O(logN) O(logN)**：N为二进制位数，这里是32。当1的个数比较多的时候，这种方式的时间复杂度要低一些，固定的只需要5步。

**空间复杂度  O ( 1 ) O(1) 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。

1.  n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);  
    无优化
2.  n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);  
    这个优化方式是这样考虑的，因为这里刚好是8个位置为一组，也就是个字节，做多有8个1，二进制表达最大为0000\_1000，有后面4位就已经够用了，所以可以先用(n + (n >>> 4))把后面4位算出来，再&0f0f将前4位清空，优化为：n = (n + (n >>> 4)) & 0x0f0f0f0f，少了一次&运算。
3.  n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);  
    同方法3一样，这里是16位为一组，最多16个1，二进制表达最大为0000\_0000\_0001\_0000，前8位全是0，可以暂时忽略，可以先用后8位相加，然后再清空前8位。  
    优化为：n = (n + (n >>> 8)) & 0x00ff00ff。
4.  n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);  
    同上，优化为：n = (n + (n >>> 16)) & 0x0000ffff。
5.  进一步观察，会发现，第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;
        }
    }

复杂度同解法三。

[leetcode]: https://leetcode.cn/problems/number-of-1-bits/description/
[Link 1]: https://blog.csdn.net/justyuze/article/details/128377045?spm=1001.2014.3001.5502
[1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7da017217ef24b76ac74e07b1ec559be.png
[1_-]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2269f0a6b8e94a719c16c5d71d3a9752.png
[1_- 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0f80524526d74841b48b265d03101acb.png