本文共 1133 字，大约阅读时间需要 3 分钟。
1.腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
思想:用数组来存这40亿个数，而且只能用bit来表示。why？40亿约等于4G，就算你用一个字节来，也需要4GB，32位的机子爆掉了。如果用bit来存，意思一个字节就能表示8个数，这个样子只需要512M内存。这个属于接受范围。如果有内存要求，则可以分块。
如何用bit位表示某个数？下面以1为例。
- 1/8=0，即存在数组的第0位。
- 1%8=1，即存在数组第0位的char的第1位，将该位置为1。
在举个例子，12345。 #include #include #include using namespace std; void setBit(char *arr,unsigned int num); int isSet(char *arr,unsigned int num); unsigned char tag[8]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01}; int main() { char * arr=new char[5242880];//512M memset(arr,0,5242880); unsigned int num; fstream in("1.txt",ios::in); while(in>>num) { setBit(arr,num); } in.close(); cout<<"初始化完毕..."< >num) { if(isSet(arr,num)!=0x00) { cout< <<"在数组中"<
- 12345/8=1543，即数组的第1543位
- 12345%8=1，即存在数组的第1543位的char的第1位，将该位置为1。
我们以16进制来表示char中每一位单独置为1的情况，即0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01。
如何判断将某一位置为1？
以将a[0]的第二位置为1为例，用位或。a[0]=a[0] | 0x20；
判断某一位是否置为1？
判断a[0]的第二位是否置为1，用位与，a[0] &0x20.如果置为1，返回非0，否则返回0.
转载地址：http://magsi.baihongyu.com/