C 面试题 求大师指教！谢谢！
题目是：随机产生100000000个取值范围为[0,2的32次方减1]的数据，然后让用户输入一个数据，判断用户输入的数据是不是包含在前面随机产生的数据中。要求：当用户输入完成后，必须在1毫秒(千分之一秒)之内完成判断。
我的思路是这样的：new出一块大小为:0xfffffffful/32的空间pData，初始化都为0；然后随机生成的数 uNum/32得到下标，然后把这随机数所以所在数组的值pData[uNum/32] |= (1<<uNum%32),即用值的所在比特位置1来保存（有生成）；所有随机数生成后，输入一个数据 nInVale,查：pData[nInVale/32]值对应所在的位：nInVale%32是否为1来判断；这样的思路如果能成也是太耗内存，要开2的32次方/32 大的地址，伤不起啊，大神请帮开下别的思路。
我看到有一个这样的思想比较好，可我做起来还有难度：创建一个足够大的位图，初始的时候将内容都置为0，然后编程随机生成数据，通过计算得到这个数据在位图中放置的位置，然后将此位置的值设置成1，循环完成数据填入。用户输入一个数据，计算在位图中的位置，然后取位图的值，值为1就表示输入值前面随机产生的数据中。我的难处在位图怎创建，怎初始化，和象素的比特位数有关吗？如果大师这方法能实现，请指教我的疑点。
谢谢啦！！！！！！！！！！！！
[解决办法]
提供几种比较靠谱的算法：
1.用哈希表来保存产生的随机数，这样在查找是就可以快很多。
2.在产生随机数时就对随机数进行排序，然后在用户输入要查找的值时对有序的数组进行二分查找，这样也可以快很多。
[解决办法]
这是典型的hash表运用，由于是随机数，你可以直接把随机数当作hash值~
1：声明 200000000（其实最好是个质数)的整形数组 array，设置为-1，
2：把随机的数 X / 200000000, 求得 下标 Index, 如果 array[index] 处是 -1，就直接把 X放进去，如果不是就看 index + 1(这个地方还有更好的方法解决碰撞）的位置是否是-1 ，直到把X放进去。
查找的时候， 直接把要查找的数 Y / 200000000 获取index ,
while (array[index] != -1)
{
if(array[index] == Y)
return true;
else
index ++;
}
return false;
你可以查找关于Hash表的相关资料，我写的就最简单的Hash表应用
[解决办法]
- C/C++ code
//随机产生100000000个取值范围为[0～2的32次方减1]的数据，//然后让用户输入一个数据，判断用户输入的数据是不是包含在前面随机产生的数据中。//要求：当用户输入完成后，必须在1毫秒(千分之一秒)之内完成判断。#include <stdio.h>#include <stdlib.h>#include <time.h>#include <malloc.h>long int i;unsigned long ul;unsigned long *d;unsigned long ulrand(void) { return ( (((unsigned long)rand()<<24)&0xFF000000ul) |(((unsigned long)rand()<<12)&0x00FFF000ul) |(((unsigned long)rand() )&0x00000FFFul));}void main() { d=(unsigned long *)calloc(1<<(32-5),sizeof(unsigned long)); if (NULL==d) { printf("Can not calloc(%d,%d)!\n",1<<(32-5),sizeof(unsigned long)); return; } srand(time(NULL)); for (i=0;i<100000000;i++) { while (1) { ul=ulrand(); if (0==(d[ul>>5]&(1lu<<(ul%32)))) { d[ul>>5]|=1<<(ul%32); break; } } if (0==i%1000000) printf("%09d,%10lu\n",i,ul); } while (1) { printf("\nInput a number:"); fflush(stdout); rewind(stdin); if (1==scanf("%lu",&ul)) break; } if (d[ul>>5]&(1<<(ul%32))) printf("Include.\n" ); else printf("Not include.\n"); free(d);}//000000000,2135468533//001000000,2465805973//002000000,3844079964//003000000,1883232874//004000000,1204697784//005000000,4050838287//006000000,3802081245//007000000,1586042671//008000000,3119931368//009000000, 251096899//010000000,3491239701//011000000,3365323844//012000000,2191846708//013000000,1879478195//014000000,1112631457//015000000,1927301519//016000000,1717332861//017000000,2922278240//018000000, 694854106//019000000, 273255526//020000000, 398518467//021000000,3270756812//022000000,1500289424//023000000,1502241936//024000000,1770380660//025000000,3668842116//026000000,3255869879//027000000,1299184024//028000000,1072990028//029000000, 242094712//030000000,3789344297//031000000,2599365925//032000000, 962754138//033000000,2055075654//034000000,4083452879//035000000, 489250842//036000000, 611455230//037000000, 277350616//038000000,1597410795//039000000,3224173662//040000000,2291446877//041000000,2546280575//042000000,2509145642//043000000,2371773252//044000000, 635555963//045000000,2674538666//046000000,4253690312//047000000,2675755514//048000000,1269320296//049000000,3172516920//050000000,1430265210//051000000, 196156173//052000000,2470825669//053000000,2536750977//054000000,1182829949//055000000,3202826434//056000000,2263336265//057000000, 313302924//058000000,3630264578//059000000,1154892716//060000000,2985304230//061000000,1252204837//062000000,1292076720//063000000, 242249250//064000000,3999999961//065000000, 431166416//066000000,1366947236//067000000,1414387330//068000000,2143784481//069000000,3242175409//070000000,4158065163//071000000,1425449573//072000000,2493600232//073000000,1316783455//074000000,3723170478//075000000,3064111466//076000000, 408557403//077000000,3722586955//078000000,3801652651//079000000,3788160154//080000000,3329440047//081000000,1408976868//082000000, 471838899//083000000,2145198260//084000000,3781081738//085000000,3439027738//086000000,1150808750//087000000,2782578638//088000000, 85604584//089000000,2704078162//090000000, 584840269//091000000,3854577719//092000000,2823653537//093000000, 797877025//094000000,2248017755//095000000,1787038685//096000000,2816548567//097000000, 489107494//098000000, 911680090//099000000,3677777147////Input a number:3677777147//Include.