-
Notifications
You must be signed in to change notification settings - Fork 0
/
Counting Bits.cpp
45 lines (39 loc) · 1.01 KB
/
Counting Bits.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
///@file Counting Bits
///@author zhaowei
///@date 2016.03.29
///@version 1.0
///@date 2016.04.07
///@version 1.1
#include <vector>
using namespace std;
class Solution {
public:
///@brief 计算从0到num的整数二进制表示的1的数目
///@param num 自然数
///@return 返回从0到num的整数二进制表示的1的数目
///@note 1. 通过观察发现,从2^(k-1)+1到2^k的二进制整数的1数目是从0到2^(k-1)的1数目加1
// 2. 时间复杂度为O(n),空间复杂度为O(n)。one-pass搞定。
vector<int> countBits(int num) {
vector<int> binary_flg;
int n = 1;
while(n < INT_MAX && n >= 0) {
binary_flg.push_back(n);
n *= 2;
}
vector<int> rslt(num+1, 0);
for (int j = 1; binary_flg[j-1] <= num; j++) {
for (int k = 0; k < binary_flg[j] - binary_flg[j-1]; k++) {
if (binary_flg[j-1] + k <= num)
rslt[binary_flg[j-1]+k] = rslt[k] + 1;
else
return rslt;
}
}
return rslt;
}
};
int main() {
Solution slt;
vector<int> rslt = slt.countBits(10);
return 0;
}