Bitmap算法

    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面可以大大节省。算法思想比较简单，但关键是如何确定十进制的数映射到二进制bit位的map图。

优点：
    1.运算效率高，不许进行比较和移位；
    2.占用内存少，比如数据N=10000000；只需占用内存为N/8=1250000Byte=1.25M。
缺点：
    所有的数据不能重复，即不可对重复的数据进行排序和查找。    


    假设有一文件里面存储了大量的数据且以升序的方式排列，例如以下形式：

3
6
7
16
23
57
89

   
      测试代码如下：

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

#define MAXLINE 1024
#define CHAR_BIT_LEN    8

static int bitmap_setbit(char *pos, int base, int new)
{
    if(pos == NULL || (new < base))
        return -1;

    pos += (new - base)/CHAR_BIT_LEN;
    *pos |= 1<<((new - base)%CHAR_BIT_LEN);

    return 0;
}

static int bitmap_checkbit(char *pos, int base, int data)
{
    if(pos == NULL || (data < base))
        return 0;

    pos += (data - base)/CHAR_BIT_LEN;

    return (*pos & (1<<((data - base)%CHAR_BIT_LEN)) ? 1:0);
}

int main(int argc, char **argv)
{
    FILE *fp = NULL;
    char line[MAXLINE] = {0};
    int linesNum = 0;
    int base;
    char pos[256] = {0};

    fp = fopen(argv[1], "r");
    if(fp == NULL) {
        printf("can not open file %s\n", argv[1]);
        return -1;
    }

    while ((fgets(line, MAXLINE, fp)) != NULL) {
        line[strlen(line)-1] = '\0';
        if(++linesNum == 1)
            base = atoi(line);

        bitmap_setbit(pos, base, atoi(line));
        if(bitmap_checkbit(pos, base, atoi(line)) == 1)
            printf("sucess:data checked in file!\n");
        else
            printf("fail:data not in file\n");
    }

    if(bitmap_checkbit(pos, base, 78) == 1)
        printf("sucess:data checked in file!\n");
    else
        printf("fail:data not in file\n");

    fclose(fp);
    fp = NULL;

    return 0;
}