每日一题：比特位个数
题目338：比特位计数给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 示例1：
[*]
输入: 2输出: 示例2：
[*]
输入: 5输出: 进阶:
[*] 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
[*] 要求算法的空间复杂度为O(n)。
[*] 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
分析
做此题首先需要知道如何计算一个数的比特位的个数。可以通过(x & x-1)每次消除数字二进制表示形式的最后一个1，代码如下：
[*]
int count(int num) { int n = 0; while (num != 0) { ++n; num = (num & num-1); } return n;}根据上面计算二进制1个数的代码分析，我们可以用dp表示数字i的比特位个数，知道dp和dp相差1个比特位个数，所以就有dp=dp+1直接看代码：代码
方法1：
[*]
class Solution {public: int count(int num) { int n = 0; while (num != 0) { ++n; num = (num & num-1); } return n; } vector<int> countBits(int num) { vector<int> dp(num+1, 0); for (int i = 0; i <= num; ++i) { dp = count(i); } return dp; }};方法2：
[*]
class Solution {public: vector<int> countBits(int num) { vector<int> dp(num+1, 0); for (int i = 1; i <= num; ++i) { dp = dp + 1; } return dp; }};
文档来源：51CTO技术博客https://blog.51cto.com/u_12444109/3031843
页:
[1]