bitmap实现数据查找和排序

/*位图排序 2011.10.18*/ 
#include 
#define MAX 1000000
#define SHIFT 5           
#define MASK 0x1F
#define DIGITS 32
int a[1+MAX/DIGITS];

void set(int n)     //将逻辑位置为n的二进制位置为1 
{
    a[n>>SHIFT]=a[n>>SHIFT]|(1<<(n&MASK));     //n>>SHIFT右移5位相当于除以32求算字节位置，n&MASK相当于对32取余即求位位置，
}                                              //然后将1左移的结果与当前数组元素进行或操作，相当于将逻辑位置为n的二进制位置1.  

void clear(int n)
{
    a[n>>SHIFT]=a[n>>SHIFT]&(~(1<<(n&MASK)));   //将逻辑位置为n的二进制位置0，原理同set操作 
}

int test(int n)
{
    return a[n>>SHIFT] & (1<<(n&MASK));        //测试逻辑位置为n的二进制位是否为1 
}

int main(int argc, char *argv[])
{
    int i,n;
    for(i=1;i<=MAX;i++)
    {
        clear(i);
    }    
    while(scanf("%d",&n)!=EOF)
    {
        set(n);
    }
    for(i=1;i<=MAX;i++)
    {
        if(test(i))
            printf("%d ",i);
    }
    return 0;
}

/*位图排序C++STL实现 2011.10.19*/ 
#include 
#include 
#define MAX 1000000
using namespace std;

bitset1> bit;        //声明一个有(MAX+1)个二进制位的bitset集合，初始默认所有二进制位为0 

int main(int argc, char *argv[])
{
    int n,i;
    while(scanf("%d",&n)!=EOF)
    {
        bit.set(n,1);          //将第n位置1               
    }    
    for(i=0;i<=MAX+1;i++)
    {
        if(bit[i]==1)
            printf("%d ",i);
    }
    return 0;
}

本文源自：

http://blog.csdn.net/ts173383201/article/details/7846161