c++刷leetcode（338. 比特位计数）【位运算】

糖逗

题目描述：

1. 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: 2
   
6. 输出: [0,1,1]
   
7. 示例 2:
   
8. 
   
9. 输入: 5
   
10. 输出: [0,1,1,2,1,2]
    
11. 
    
12. 来源：力扣（LeetCode）
    
13. 链接：https://leetcode-cn.com/problems/counting-bits
    
14. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     vector<int> countBits(int num) {
   
4.         vector<int> result(num+1);
   
5.         result[0] = 0;
   
6.         for(int i = 1; i <= num; i++){
   
7.             if(i % 2 == 1){
   
8.                 result[i] = result[i-1] + 1;
   
9.             }else{
   
10.                 result[i] = result[i/2];
    
11.             }
    
12.         }
    
13.         return result;
    
14.     }
    
15. };

复制代码

参考链接：https://leetcode-cn.com/problems ... de-si-lu-by-duadua/
注意事项：
1.规律：奇数：二进制表示中，奇数一定比前面那个偶数多一个 1
二进制表示中，偶数中 1 的个数一定和它前一个偶数除以 2 之后的那个数一样多。