LeetCode:191. 位1的个数;338. 比特位计数

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

提示:

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

示例 :

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

首先想到的当然是,int的32位,对每一位做是否1的判断,那么在位运算中,一般采用&1来得到是否是1。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        //int类型4字节32位,每一位与1做与计算,累加结果为1的数量即可
        int sum = 0;
        for(int i=0;i<32;i++){
            if((n & (1<<i)) ==0){
                continue;
            }
            sum++;
        }
        return sum;
    }
    
}

时间复杂度O(k),k是一个常量32。空间复杂度O(1)。

 

位运算优化:

观察这个运算:n & (n−1),其运算结果恰为把n的二进制位中的最低位的1变为0之后的结果。如:6&(6-1) = 4

,运算结果 4即为把 6的二进制位中的最低位的 11 变为 00 之后的结果。

这样我们可以利用这个位运算的性质加速我们的检查过程,在实际代码中,我们不断让当前的n与n−1做与运算,直到n变为0即可。因为每次运算会使得n的最低位的1被翻转,因此运算次数就等于n的二进制位中1的个数。

public class Solution {     // you need to treat n as an unsigned value     public int hammingWeight(int n) {         int sum = 0;         while (n!=0){             n &= n-1;             sum++;         }         return sum;     }      }

时间复杂度:O(log(n)),空间复杂度:O(1)。

 

java里面有一个直接求解的方法:Integer.bitCount(),可以说再次将运算做了优化,来看下源码:

public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

具体这个方法的分析:https://blog.csdn.net/qq_27007509/article/details/112246576

 

338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 :

输入: 2
输出: [0,1,1]

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗?

这个主要在于找出规律:

当i为偶数,末位永远是0,所以比特位i=i/2,也就是右移1位;

当i为奇数,末位永远是1,所以比特位i=i/2+1,也就是右移1位再+1;

有这个关系,因而想到了动态规划。

class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num+1];
        for(int i=1;i<=num;i++){
            bits[i] = bits[i>>1]+(i&1);
        }
        return bits;
    }
}

遍历了一遍:时间复杂度:O(n)

 

上一篇:338 . 比特位计数


下一篇:【LeetCode】338. 比特位计数