剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

这道题，其实就是需要实现一个二进制加法：add1 + add2 = result，然后计算result中的1的值。只不过每一次加法的 add2 都等于二进制1。同时将result的结果更新为 add1。add1的初始值为0，n为几就计算几次。画个图大家应该就能明白：

 因此，最关键的一步是实现二进制加法，然后返回加法的结果，统计结果中1的个数，push_back到结果数组中即可。而二进制加法已经在第二道题中实现了，因此就比较简单了。

#include
#include
#include
using namespace std;

class Solution {
public:
	vector countBits(int n) {
		vector ansnum{ 0 };
		if (n == 0) return ansnum;

		string first = "0";
		const string second = string(1, (1 + '0'));
		for (int i = 1; i <= n; i++) {
			string tmpstr = bitadd(first, second);
			int cnt = 0;
			for (char tmpch : tmpstr) {
				if (tmpch == '1') {
					cnt += 1;
				}
			}
			ansnum.push_back(cnt);
			first = tmpstr; // 更新first值			
		}
		return ansnum;
	}
	string bitadd(string a, string b) {
		int alen = a.length(), blen = b.length();
		int minlen = min(alen, blen);

		int step = 0;
		vector ans;
		for (int i = 0; i < minlen; i++) {
			int ad1 = a[alen - 1 - i] - '0', ad2 = b[blen - 1 - i] - '0';
			int tmpsum = ad1 + ad2 + step;
			if (tmpsum >= 2) {
				ans.push_back((tmpsum) % 2);
				step = (tmpsum) / 2;
			}
			else {
				ans.push_back(tmpsum);
				step = 0;
			}
		}
		if (alen == minlen && blen != minlen) {
			// b开始
			cout << "in b" << endl;
			int instep = step;
			for (int i = minlen; i < blen; i++) {
				int ad1 = b[blen - 1 - i] - '0', ad2 = instep;
				int tmpsum = ad1 + ad2;
				if (ad1 + ad2 >= 2) {
					ans.push_back((tmpsum) % 2);
					instep = (tmpsum) / 2;
				}
				else {
					ans.push_back(tmpsum);
					instep = 0;
				}
			}
			if (instep == 1) {
				ans.push_back(instep);
			}
		}
		else if (blen == minlen && alen != minlen) {
			// a开始
			cout << "in a" << endl;
			int instep = step;
			for (int i = minlen; i < alen; i++) {
				int ad1 = a[alen - 1 - i] - '0', ad2 = instep;
				int tmpsum = ad1 + ad2;
				if (ad1 + ad2 >= 2) {
					ans.push_back((tmpsum) % 2);
					instep = (tmpsum) / 2;
				}
				else {
					ans.push_back(tmpsum);
					instep = 0;
				}
			}
			if (instep == 1)
				ans.push_back(instep);
		}
		else {
			// 长度相等
			if (step == 1) {
				ans.push_back(step);
			}
		}
		string ansstr = "";
		for (int i = ans.size() - 1; i >= 0; i--) {
			char tmpchar = ans[i] + '0';
			ansstr += tmpchar;
		}
		// cout< cnts = s.countBits(5);
	cout << endl;
	for (int cnt : cnts) {
		cout << cnt << " ";
	}

	return 0;
}