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