比特位计数

给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans。

约定

• 0 <= n <= 10^5

输入

• n：非负整数

输出

长度为 n + 1 的数组，ans[i] 为 i 的二进制中 1 的个数。

示例一

输入：

n = 2

输出：

[0, 1, 1]

示例二

输入：

n = 5

输出：

[0, 1, 1, 2, 1, 2]

复杂度要求

• 时间复杂度：O(n)
• 空间复杂度：O(1)（不计返回值）