一、題目描述

二、解題思路

我們可以借助位運算的思想來解決這個問題。通過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;}
};