1.题目

2.思路

k&=(k-1)实现每次去掉最右边的1，从而统计出每个数的二进制的1的个数。
位运算的技巧还有异或等（【LeetCode136】只出现一次的数字（不能用哈希，用位运算-异或））。

3.代码

class Solution {
public:
    int count(int k){
        int cnt=0;//置0
        while(k>0){
            cnt++;//1的个数增加
            k&=(k-1);//每次去掉最右边的一个1
        }
        return cnt;
    }
    vector<int> countBits(int num) {
        vector<int>bits(num+1);//注意不是num大小
        for(int i=0;i<=num;i++){
            bits[i]=count(i);
        }
        return bits;   
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

4.时间复杂度

int型数据的二进制位数为k=32位，而0到num每个数字都要遍历k次，即时间复杂度为$O(k\times num)$。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/115551448