比hashmap节省内存。

【数据结构和方法设计】

#include <stdio.h>
#include <string.h>
#include <assert.h>

#define MAX_CNT_CHR (32)
#define MAX_CNT_BIT (MAX_CNT_CHR*8)
#define MAX_VAL_BIT (MAX_CNT_BIT-1)

unsigned char bitmap[MAX_CNT_CHR] = {};

typedef unsigned int uint;

unsigned char bitmap_isOverflow(uint num)
{   
    return (MAX_VAL_BIT < num);
}

unsigned char bitmap_isExist(uint num)
{   
    if (bitmap_isOverflow(num)) assert(0);
    
    unsigned char row = num / 8;
    unsigned char col = num % 8;
    
    return bitmap[row] & (1<<col);
}

void bitmap_init()
{
    memset(bitmap, 0x0, sizeof(bitmap));
}

void bitmap_add(uint num)
{
    assert(!bitmap_isOverflow(num));
    bitmap[num/8] |= (1<<(num%8));
}

void bitmap_rm(uint num)
{
    assert(!bitmap_isOverflow(num));
    bitmap[num/8] &= ~(1<<(num%8));
}

void bitmap_show_items(void)
{
    int i;

    for (i=0; i<MAX_VAL_BIT; i++) {
        if (bitmap_isExist(i)) printf("FOUND: %d\n", i);
    }

    printf("\n");
}

/* TC */
int main()
{
    bitmap_init();

    bitmap_add(0);
    bitmap_add(4);
    bitmap_add(4);
    bitmap_add(7);
    bitmap_add(188);
    bitmap_add(80);
    bitmap_add(98);
    bitmap_add(255);
    //bitmap_add(256);

    bitmap_show_items();
    bitmap_rm(98);
    bitmap_rm(100);

    bitmap_show_items();

    return 0;
}