位图（位矢量、位向量）

时间：2010-11-08 来源：guocai_yao

问题来源《编程珠玑II》第一章的内容

精确的问题陈述如下

输入：

所输入的是一个文件，至多包含n个正整数，每个正整数都要小于n，这里的n为10^7。如果输入时某一个整数出现了两次，就会产生一个致命的错误。这些整数与其他任何数据都不关联。

输出：

以增序形式输出经过排序的整数列表。（这里应该补充一下是文件形式吗？）

约束：

至多（大概）只有1MB的可用主存，但是可用磁盘空间非常充足。运行时间至多只允许几分钟，最适宜的时间大概为10秒钟。

实现思路

#include <stdio.h>
#include <stdlib.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1f
#define N 10000000
int a[1+N/BITSPERWORD];

void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i)
{
    a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}

int main()
{
    set(5000);
    if(test(5000)) {
        printf("5000\n");
    }else{
        printf("Not 5000\n");
    }

    clr(5000);
    if(test(5000)) {
        printf("5000\n");
    }else{
        printf("Not 5000\n");
    }

    return 0;
}

3. 参考 1) http://www.cnblogs.com/whzh/archive/2009/07/29/1533572.html 2) http://www.cnblogs.com/cnyao/archive/2009/11/26/interview8.html