剑指 Offer II 003. 前 n 个数字二进制中 1 的个数【模拟】

题目

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

难度：简单

说明 :

• 0 <= n <= 105

题解

按照题意模拟即可

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = getCount(i);
        }
        return res;
    }
    
    int getCount(int u) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            // 与1相与，判断最低位是1还是0
            count += u & 1;
            // 每次右移1位
            u = u >> 1;
            // 提前退出
            if (u == 0) {
                return count;
            }
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)