leetcode 338 比特位计数

一、题目描述

二、解题思路

我们可以借助位运算的思想来解决这个问题。通过k=k&(k-1)来消除k中最右边为1的比特位，每次消除后进行count++，当k为0时，表示所有的1消除完毕，此时的count即为所有1的个数。

三、代码实现

时间复杂度：T(n)=O(n*logn)

空间复杂度：S(n)=O(n)

class Solution {
public:vector<int> countBits(int n) {vector<int> ret;for(int i=0;i!=n+1;i++){int count=0;int k=i;while(k){count++;k=k&(k-1);}ret.push_back(count);}return ret;}
};