面试结束的这些日子好几次接触到BitMap这个东西。到底是啥呢，究其原因就是虽然它的使用条件较为苛刻，但是它对应的时间复杂度和空间复杂度真的是惊人的好。
首先是根据其思想先写了一个比较差的实现代码：
#include <iostream>
#include <cstdio> using namespace std; int main()
{
//bitmap的简单应用
//查出1到10中一共9个不重复的数字，到底少了哪个数字
long long n=;
//假设少了数字3
for(int i=;i<;i++){
if(i!=){
n^=<<(i);
printf("the n is %lld\n",n);
}
} for(int i=;i<;i++){
n^=<<(i);
}
//n^=1<<(sizeof(n)*8-2);
int ans=;
while(n>>=){
ans++;
}
printf("%d\n",ans);
return ;
}
也就是时间复杂度大概是n的样子，不过系数相对大了些。据说Java中有相对应的包来实现，想来应该会用补码的方式进行一个简单的优化吧。
我能想到的就是在合理的条件下使用lowbit的方式求出每个缺省值，这样子还可以将缺少的数字推广开来。
来自编程珠玑的简单思考
http://blog.jobbole.com/109024/?utm_source=blog.jobbole.com&utm_medium=relatedPosts