LeetCode 191
编写一个函数，输入是一个无符号整数（以二进制串的形式，长度为 32 ），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有 3 位为 '1'。
示例 2：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
方法一：循环检查二进制位
第一种最简单的方法，就是for循环判断每一位的值，如果为1，则ans++。
每次使用 2i 来进行与 n 相与,一共需要检查32位。时间复杂度：O(k)，其中 k=32
public class Solution {
public int hammingWeight(int n) {
int ans = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) {
ans++;
}
}
return ans;
}
}
方法二：优化后的位运算
观察运算 n&(n-1)，以 6&5和8&7为例：
6&5 =====> 110 & 101 = 100
4&3 =====> 100 & 011 = 000
可以发现n&(n-1)的结果，恰好是把n的二进制位中的最低位的1变为0之后的结果。
因为n变为n-1，最低位的1后边的0都会翻转为1，而最低位的1会翻转为0，所以n&(n-1)的结果为n的二进制位中的最低位的1变为0。
这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的n与n-1相与，直到n变为0为止。
时间复杂度：O(logn)。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ans=0;
while(n!=0)
{
ans++;
n=n&(n-1);
}
return ans;
}
}
方法三：
JDK 源码 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;
}
接下来我们来看这道的进阶版LC338。
LeetCode 338
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例1：
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
方法一：直接计算
根据LC191的三种方法，很容易得到时间复杂度为O(n*sizeof(integer))的解答。其中具体的复杂度和上述三种方法的复杂度有关。
class Solution {
public int[] countBits(int num) {
int[] bits = new int[num + 1];
for (int i = 0; i <= num; i++) {
bits[i] = hammingWeight(i);
}
return bits;
}
public int hammingWeight(int n) {
int ans=0;
while(n!=0)
{
ans++;
n=n&(n-1);
}
return ans;
}
}
方法二：动态规划
我们可以根据上一题n&(n-1)的性质，来构造递推式。
设y=x&(x-1)，显然0 ≤ y < x，因此有ans[x]=ans[y]+1。
所以对任意正整数x，都有ans[x]=ans[x&(x-1)]+1。for循环从 1 遍历到 num，便可计算ans[i]的值。
时间复杂度为O(num)。
class Solution {
public int[] countBits(int num) {
if(num==0)
return new int[]{0};
int[] ans=new int[num+1];
for(int i=1;i<num+1;i++)
{
ans[i]=ans[i&(i-1)]+1;
}
return ans;
}
}
