位图在随机数的排序中用途广泛，并且耗时较少，最常用的是一位位图，即用一个bit的0/1来表示一个数，如果这个数存在就把响应的bit位置为1，否则就是0。在真正使用的时候，首先遍历数列，把表示每个数的相应bit位置1，第二次遍历位图，判断相应bit位对应数字是否存在，存在就打印输出，这样的序列自动有序。

但是单bit位有一个缺点就是，可以检测元素是否存在，但是对于含有重复元素的序列排序就无能为力了。

题目：在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

这道题用2-bitmap可以很容易解决，每一个数用2-bit来表示，共可以表示4种状态,00表示不存在，01表示出现一次，10表示出现2次或者多次，11没有定义

 

2-bitmap的构造也是借助于1-bitmap，首先看一下1-bitmap的构造

#define mas 31int a[1000000];// 第0位表示数字0，第1位表示1int test(int i){    return a[i>>5] & (1<<(mas - i & mas));}void set(int i){    a[i>>5] |= 1<<(mas - i & mas);}void clear(int i){    a[i>>5] &= ~(1<<(mas - i & mas));}

2-bitmap的构造

int getT(int i){    if(!test(i) && !test(i+1))  /* 检查表示数字的两位数字 */        return 0;    else if(!test(i) && test(i+1))        return 1;    else if(test(i) && !test(i+1))        return 2;    else        return 3;}void setT(int i){    /* 检测对应位的当前值，然后进行变换 */    int t = getT(i);    switch(t)    {    case 0: set(i+1);break;    case 1: set(i);clear(i+1);break;    case 2: break;    }}/* 清除当前值 */void clearT(int i){    clear(i);    clear(i+1);}

从一系列数中找出不重复元素

int main(){    int n;    int b[100000];    scanf("%d",&n);    for(int i=0;i