计算数字的二进制中1的个数

发表于   |   分类于 ，   |  

计算二进制中1的个数问题

题目大意

　　https://leetcode.com/submissions/detail/62797806/

　　计算从0到num中每个数字的二进制形式中1的个数

题目分析

　　这个题目，暴力解法复杂度在O(n*sizeof(integer))，这里integer就是某个i的二进制表示后的长度。可以用动态规划解此贴，但关键巧妙的店在于递推公式，就是计算ret[i] (结果数组用ret表示)如何利用ret[0]~ret[i-1]的结果

　　想计算数字i的二进制中1的数量，计算i&(i-1),i&(i-1)中1的数量一定比i中1的数量少1.

　　可以这样证明：i的最后一位是0或者1

  • 如果是0，那么i-1的最后一位是1，i的倒数第二位是0的话，i-1的倒数第二位为1…….直到i的某一位为1，i-1的该位为0。从这位往前推，i和i-1都是相同的。
  • 如果是1，那么i-1的最后一位是0，其他位跟i相同

　　综上两种情况，i&(i-1)中1的个数一定比i中1的个数少1.该算法复杂度就是O(n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;
vector<int> countBits(int num) {
    vector<int> ret(num + 1, 0);
    for(int i = 1; i <= num; i++) {
        ret[i] = ret[i & (i - 1)] + 1;
    }
    return ret;
}
int main() {
    vector<int> ret = countBits(5);
    for(int i = 0;i <= 5; i++) {
        cout << ret[i] <<" " ;
    }
    cout <<endl;
    return 0;
}