位图算法的应用

位图或位向量图作为一个集合，表示的这样的一个数据结构：用字符串 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 表示集合 {1,2,3,5,8,13}.

• 位图的应用需要数据有如下的特性:
  1.输入数据限制在相对较小的范围内;
  2.数据没有重复(或剔除重复数据);
  3.除了单一整数外,没有任何其他关联数据.

如给定表示文件中整数集合的位图数据结构，则可以分为三个阶段来编写程序：

• 将所有的位都置为0，从而将集合初始化为空。
• 通过读入文件中的每一个整数来建立集合，将每一个对应的位置都置为1.
• 检查每一位，如果该位为1，就输出对应的整数，由此产出有序的输出文件。

字节位置=数据/32;(采用位运算即为右移5位)
位位置=数据%32;(采用位运算即跟0X1F进行与操作，因为0X1F=00011111,将一个数和0X1F相与就是将32的倍数全部清零，只留下余数位。)

#define MAX 10000000
#define SHIFT 5
#define MASK 0x1F
#define DIGITS 32

int a[1+MAX/DIGITS];

void set(int n)
{
    a[n>>SHIFT] |= (1<<(n&MASK));
//将1左移余数个位数即为将这个位置置1，即若将1左移6位则为将第六个bit位置1.其余全为0.
}

void clear(int n)
{
    a[n>>SHIFT] &= (~(1<<n&MASK));
//将1左移余数个位数即为将这个位置置1，再取反则为将这个bit置0，其余全为1.
}

int test(int n)
{
    return a[n>>SHIFT] &(1<<(n&MASK));
}

int main(int argc, char const *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\n",i);
    return 0;
}