面试题：怎么在一千万个不重复整数（电话号码）中查找某个特定数 位运算 bit地图
面试题：某城市有一千万个电话号码，如何快速找到某个电话号码，考虑优化时间和空间复杂度，同时考虑内存限制。
同类变形：Given 2MB memory, we want to store 5 million integers in 0~10million range. These integers are unique.
1. How to store these integers?
2.Given a target integer i, how to test whether it is existed in these 5 million integers using only 2MB memory?
思路分析：上面两题实际是一道题目，前面一个我在某个互联网公司面试遇到过。需要使用到bitmap和位运算。我们以下面一个题目为例子分析，要想用少于2MB内存存下5百万个介于0到1千万之间的整数，显然不能用通常方式保存。我们可以分析，需要用long integer去保存千万级别的整数，每个long integer整数需要4个byte（32 bit），那么5M个整数需要20MB。如何减小内存消耗更精简的保存这些整数呢？我们考虑更仔细的使用每个bit，用bitmap。所谓bitmap就是对每个bit位进行映射，注意这是逻辑上或者算法上的映射，与计算机组成原理及内存地址无关。在这题里面，我们可以把每个bit映射成一个整数，如果是32位计算机，那么32个bit可以保存32个整数，由于整数范围是0-10M，所以我们可以划分成0-31 32-63 64-95 ... 所以我们一共只需要10M/32*4=1.25MB内存，刚好满足题目要求，做完位映射后，要保存某个数字是否存在，我们只需要用1或者0来置位，存在就赋值1，否则赋值0。第二问，如果我们用一个数组int [] db保存好了这5百万个整数（用bitmap的方式，在存在对应数的位置好已经置好1），那么我们可以用位运算来测试某个数i是否存在，实例代码如下：
Boolean exist(int i){
int [] db;
//0 - 10 000 000 0-31 32-63 64-95 ... (10 000 000 - 31) 10 000 000
//i i / 32
int div = i / 32;
int remain = i % 32;
int storeNum = db[div];
return (1<<remain & storeNum);
}
关键一句是1<<remain & storeNum, 我们先求i落在那个范围内，除以32得到商和余数，然后把1左移位remain位得到10000....（remain个0），然后与storeNum取与运算即可得到对应位置是否为1，实质是clear掉i对应bit之外的其他所有bit。
位运算在Google等公司的面试中有可能出现，虽然简单，但是经常可以给出一些很巧妙很tricky的解法，要熟悉bit 与或非和异或运算的性质，知道如何get, set,clear,update某个特定的bit，通常都是左移位，右移位运算和与或非及异或运算结合实现的，比如
Get Bit
boolean getBit(int num, int i){
return ((num & (1 << i)) != 0);
}
Set Bit
int setBit(int num, int i){
return num | (1 << i);
}
Clear Bit
int clearBit(int num, int i){
int mask = ~(1 << i);
return num & mask;
}
Update Bit
int updateBit(int num, int i, int v){
int mask = ~(1 << i);
return (num & mask) | (v << i);
}
更多位运算的解析和练习题可以参考CC150 P89开始的相关章节。
最后收录几个关于位运算面试题的总结贴，有时间可以仔细看看想一想。
1 http://codeganker.blogspot.com/2014/09/leetcode_9.html
2 http://blog.tomtung.com/2007/05/bitwise-operation/
3 http://blog.****.net/morewindows/article/details/7354571