首页 » 编程语言 » c&c++ » 统计一个二进制字符串中1的个数的算法

统计一个二进制字符串中1的个数的算法

 

记得在吴军的《数学之美》中有一章讲到布尔代数和搜索引擎的索引。大概是讲通过一个二进制字符串来标识当前关键词在那些文档中出现过。二进制字符串中1的位置就是出现这个词文档的id。
如,一淘 对应一个二进制字符串 1010001。其中在1,5,7三个位置出现了1,说明文档id为1,5,7的文章包含词“一淘”。但是在书中没有说如何统计1的个数和位置。现在我补充以下实现算法。
代码如下:

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int main(){
	int n = 10002;
	int num = 0; //1的个数
	int tmp = n;
	vector<double> pos; //1的位置
	while (n)
	{
		n &= (n-1);
		num++;
		pos.push_back(log2(tmp-n) + 1);
		tmp = n;
	}
	cout << "the number of 1 is " << num << endl;
	cout << "the position is " << endl;
	for (vector<double>::iterator i = pos.begin(); i != pos.end(); i++)
	{
		cout << *i << endl;
	}
}

输出结果:
the number of 1 is 6
the position is
2
5
9
10
11
14

技术交流

原文链接:统计一个二进制字符串中1的个数的算法,转载请注明来源!

原文链接:统计一个二进制字符串中1的个数的算法,转载请注明来源!

1