【力扣】：比特位计数

1.去掉二进制中最左边的1，n&（n-1），如果一次操作以后，就是0，那么这个数是2的倍数。进行几次操作，，变为0，那么就有几个1.

2.拿到最左边的1，n&-n

3.将x位改为0,~（1<<x）&n

4,x位改为1，1<<x|n.

 解法一：
 

class Solution {
public:vector<int> countBits(int n) {vector<int> bits(n + 1);for (int i = 0; i <= n; i++) {int ones = 0;while (x > 0) {x &= (x - 1);ones++;}bits[i]=ones;}return bits;}
};

解法2：

动态规划

class Solution {public int[] countBits(int n) {int[] bits = new int[n + 1];int highBit = 0;for (int i = 1; i <= n; i++) {if ((i & (i - 1)) == 0) {highBit = i;}bits[i] = bits[i - highBit] + 1;}return bits;}
}