# 338. Counting Bits

## 描述

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:

For num = 5 you should return [0,1,1,2,1,2].

Follow up:

1.It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?

2.Space complexity should be O(n).

3.Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

## 分析

/*compute every bit then judge if it equals 1*/
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res(num+1,0);
for(int i=0;i<=num;i++){
for(int j=0;j<32;j++){
if(i!=0&&(i>>j)&1==1)
res[i]++;
}
}
return res;
}
};


0000    0
-------------
0001    1
-------------
0010    1
0011    2
-------------
0100    1
0101    2
0110    2
0111    3
-------------
1000    1
1001    2
1010    2
1011    3
1100    2
1101    3
1110    3
1111    4


/*make use of what you have produced*/
class Solution {
public:
vector<int> countBits(int num) {
if(num==0)
return {0};
vector<int> res{0,1};
int k=1,i=1;
while(i<=num){
for(i=pow(2,k);i<pow(2,k+1);i++){
if(i>num)
break;
int tmp=(pow(2,k+1)-pow(2,k))/2;
if(i<pow(2,k)+tmp)
res.push_back(res[i-tmp]);
else
res.push_back(res[i-tmp]+1);
}
k++;
}
return res;
}
};


class Solution {
public:
vector<int> countBits(int num) {
vector<int> res{0};
for(int i=1;i<=num;i++){
if(i%2==0)
res.push_back(res[i/2]);
else
res.push_back(res[i/2]+1);
}
return res;
}
};


2016-10-20

### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017