文章目录

题目描述示例示例 1示例 2 题解代码

题目描述

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例

输入 输入一个非负整数 num 输出 输出 0 ~ num 中的每一个数字对应二进制数的 1 的数目

示例 1

输入： 2 输出： 0 1 1

示例 2

输入： 5 输出： 0 1 1 2 1 2

题解

由于 n & (n - 1) 可以消去 n 对应的二进制数的最后一位 1 ，那么以此可以求出计算 n 对应的二进制数中的 1 的个数。

由于要求出 0 ~ num 每一个数对应的二进制数中的 1 的个数。如果分别求解，则有大量重复计算，可以建立记录表保存已求解的结果。因为 n & (n - 1) < n 那么 n & (n - 1) 在 计算 n 时已计算，n 中 1 的个数比 n & (n - 1) 多 1 。

代码

#include <iostream> using namespace std; const int size = 1000; int main() { int num = 0; cin >> num; int a[size]; a[0] = 0; cout << 0 << " "; for (int i = 1; i <= num; i++) { a[i] = a[i & i - 1] + 1; cout << a[i] << " "; } return 0; }

返回顶部