位图算法

已空间换时间。

很多不重复的整数，其中最大值不超过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

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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;
}