位图算法

#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;
}