力扣 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

题目来源：https://leetcode-cn.com/problems/w3tCBm/

大致题意：
给一个整数 n，求出 1 - n 每个数的二进制中 1 的个数

思路

1. 遍历所有数，使用 Java Integer 类的 bitCount(int) 方法可以直接求出对应数的二进制中 1 的个数
2. 使用动态规划

动态规划

对于数 i 和 j，若 j 的二进制中 1 的个数只比 i 中的多一个，那么 j 中 1 的个数即为 i 中 1 的个数 +1

在递增遍历时，如何求出比当前的数的二进制刚好小 1 的数

• 去掉当前数二进制最高位 1 的数正好比当前的数的二进制刚好小 1

所以可以用一个整数 highBit，表示当前最高位为 1 的数，只要用当前遍历的数减去 highBit，得到的数即为比当前的数的二进制刚好小 1 的数，然后当前数二进制中 1 的个数即为所得到数的个数 +1

代码：

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];	// 存每个数对应的二进制中 1 的个数
        ans[0] = 0;
        int highBit = 1;	// 当前的数的最高位 1 表示的数
        for (int i = 1; i <= n; i++) {
        	// 如果当前数是 2 的幂次，更新 highBit
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            // 求出当前数对应的二进制中 1 的个数
            ans[i] = ans[i - highBit] + 1;
        }
        return ans;
    }
}