ビットカウント(アルゴリズム)

ビットカウント(アルゴリズム)

  :      
        n,
  0 <= i<= n       i, 
        1   ,
          .

n=2,0,1,2出力:[0,1,1]
1.for i=0=>n:count bits(i)2.count[n+1]for i=0=>ncount[i]=count[i&(i-1)]+1
java

vector<int> countBits(int num) {
    vector<int> bits(num + 1, 0);
    for (int i = 1; i <= num; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}