大数据量算法_大数据量计算

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

位图思想解法：

#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
 
#define MAX_NUM (4294967295) 
 
int main(void)
{
	unsigned int inputNum[4]={1,2,3,MAX_NUM};
	unsigned int testNum1 = MAX_NUM;
	int i = 0;
 
	unsigned char *mapMem = (unsigned char *)malloc((MAX_NUM)*sizeof(unsigned char)/8 +1);
	memset(mapMem,'\0',((MAX_NUM)*sizeof(unsigned char)/8 +1));
 
	
	for (i = 0; i<4; i++)
	{
		mapMem[inputNum[i]/8] |= (1 << (inputNum[i]%8));
	}
 
	//test
	if (mapMem[testNum1/8] & (1 << (testNum1%8)))
	{
		printf("%d is in the array\n",testNum1);
	}
	else
	{
		printf("%d isn't in the array\n",testNum1);
	}
	
	free(mapMem);
 
}