位图算法
已空间换时间。
很多不重复的整数，其中最大值不超过40亿，最小值是0，要求判断某个指定的整数，是否在这个集合中。
使用2个字节，表示16个数，的状态(有或者没有)
上面为表示的数，下面为该数的个数。
15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
例如：要表示1,13,4,5,6
15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
要表示40亿个数
4000000000/8 = 500000000字节
500000000字节/1024= 488281K
488281k/1024 = 476.837M
单位换算
1字节== 8比特位
1K == 1024字节
1M == 1024K
代码实现：
代码语言：javascript复制#include<iostream>
using namespace std;
//初始化容器内容
void init(char* data, int len)
{
unsigned int tempN = len * 8;//40亿个数——40亿个位
//假定需求:这个容器中存的是40亿以前能被3整数的数
//就将他对应的比特位改成1(默认是0——memset())
for (unsigned int i = 0; i < tempN; i )
{
if (i % 3 == 0)
{
//找到这个数对应的字节
char* p = data (i / 8);
//找到对应的位，并且将对应的位改成1
*p = *p | (1 << (i % 8));//解释如下:
/*
如何将这个数对应的位(在比特位中的第几位数)改成1？
对1进行左移操作,这个数 % 8等于多少
(就是该数与该字节的最右侧中间间隔了几个位)，
1就左移几位，
然后和这个字节进行按位或操作，例如
i = 12;
//上面是对应的数,下面是对应比特位的数
15 14 13 12 11 10 9 8
0 0 0 0 0 0 0 0
与 1 << (i % 8) 进行按位或操作
0 0 0 1 0 0 0 0
得到
15 14 13 12 11 10 9 8
0 0 0 1 0 0 0 0
*/
}
}
}
//位图算法实现
bool check(char* data,int len,int value)
{
//找到对应的字节
char* p = data value / 8;
//找到对应的位，并判断是否存在
bool ret = *p & (1 << (value % 8));//解释如下
/*
对1进行的左移操作同上
然后将这个所在的字节与1左移后的值，进行按位与
1 & 1 = 1
1 & 0 = 0
0 & 0 = 0
0 &1 = 0；
*/
return ret;
}
int main(void)
{
unsigned int n = 4000000000;//这个40亿代表40个数(80亿个比特位)
int len = n / 8 1;//40亿个数对应的字节个数
char* data = new char[len];//创建对应字节个数这么大的一个数组(容器)
memset(data, 0, len);//容器清0
init(data, len);//往容器中存数据
int a = 0;
//输入测试
while (1)
{
cout << "请输入你要查找的数" << endl;
cin >> a;
if (a == -1)
{
break;
}
if (check(data, len, a))
{
cout << a << "被找到啦" << endl;
}
else
{
cout << a << "找不到" << endl;
}
}
return 0;
}
