文章目录

• • 题目描述
  • 解题思路一
  • 解题思路二

题目描述

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

示例1：

输入: 2
输出: [0,1,1]

示例2：

输入: 5
输出: [0,1,1,2,1,2]

进阶:

• 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
• 要求算法的空间复杂度为O(n)。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

来源：力扣（LeetCode）ttps://leetcode-cn.com/problems/counting-bits

解题思路一

看到这题，二话不说，直接想到十进制转二进制使用除2取余法来做！

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
	vector<int> countBits(int num) {
		vector<int> v;
		for (int i = 0; i <= num; i++) {
			int quo = i;								//商
			int count = 0;							//记录这个数转变成二进制有多少个1
			while (quo > 0) {						//除2取余法
				if (quo % 2>0) {
					count++;
				}
				quo = quo / 2;
			}
			v.push_back(count);
		}
		return v;
	}
};

int main() {
	Solution s;
	vector<int> v;
	v=s.countBits(5);
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

运行结果(同样的代码多提交几次，运行结果会不一样，这个代码最差需要20ms)：

解题思路二

解题思路一比较简单，运行效率不高，既然要求二进制1的个数，更快的方法是直接使用位运算！

每个int 型的数都可以用 32 位二进制数表示，只要遍历其二进制表示的每一位即可得到 1 的数目。利用为运算的技巧，可以在一定程度上提升计算速度。按位与运算(&)的一个性质是：对于任意整数x，令x=x&(x-1)，该运算将x的二进制表示的最后一个1变成0。因此，对x重复该操作，直到x变成0，则操作次数即为x的关于1的比特数！例如下图的例子，假设x=53

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> bits;
        for (int i = 0; i <= num; i++) {
            int ones = 0;                              //记录二进制1的个数
            int x = i;
            while (x > 0) {                            //按位与运算
                x &= (x - 1);
                ones++;
            }
            bits.push_back(ones);
        }
        return bits;
    }
};

int main() {
	Solution s;
	vector<int> v;
	v=s.countBits(5);
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

运行结果(运行多次最好的一次，稍微比解题思路一效率要高)