1221 - 比特位计数

通过次数

8

提交次数

36

时间限制 : 1 秒
内存限制 : 128 MB

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

输入

一个整数n

输出

从0到n所有数字的二进制中1的个数

样例

输入

2

输出

0
1
1

输入

5

输出

0
1
1
2
1
2

提示

0 \leq n \leq 10^5