编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '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)