比特位计数(算法)

题目: 比特位计数 给定一个非负整数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 => n; count[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; }