//采用位图的方法，如果是在一个1000万大的数组中，其中只有两个数是相同的，可以在O(n)时间复杂度内找出相同的数
//数组b是一块连续内存区域，用数组中的每一bit表示一个数是否存在，1表示存在，0不存在，比如，给定一个数字1025，
//那么，就把b数组的第1025bit置为1，基本思想就是用数组内存的一个bit所在的下标值作为数据数值，而不用真正去储存这个值，用下标作为值，节省空间。
//因为操作系统内存最小操作单位是字节，所以不能直接操作bit，因此，首先，必须找到第1025bit所在的字节，就是1025/8（因为下标是从0开始，整除截断的无关紧要，下步用到），
//然后再找出1025在该字节的哪一bit，就是1025%8=1，整个意思就是，1025在b数组的第1025/8个字节的第1 bit中，然后用&操作访问该bit是否为1，为1则表明1025存在了.
#include <stdio.h>
int a[3]={1,10000000,10000000};
//char类型为8位，共需要10000000/8个char
static unsigned char b[10000000/8+1];
int i;
void main() {
for (i=0;i<3;i++) {
//1<<(a[i]%8)表示1左移余数的位数即为a[i]在b中对应的位，例如1024%8=0，然后1<<0=1(二进制止：00000001)，所以1024在b数组的第1024/8个字节的第1 bit中;
//1025%8=1，然后1<<1=2(二进制：00000010)，所以1025在b数组的第1025/8个字节的第2 bit中;1026%8=2，然后1<<2=4(二进制：00000100)，所以1026在b数组的第1026/8个字节的第3 bit中;以次类推
if (b[a[i]/8]&(1<<(a[i]%8))) break;
else b[a[i]/8]|=(1<<(a[i]%8));
}
if (i<3) printf("%d\n",a[i]);
else printf("Can not find.\n");
printf("%d\n",1<<(1024%8));
printf("%d",5);
}
