算法學習 - bitmap實現(c++)

BitMap介紹

這裡的BitMap指的是把數據存放在一個以bit為單位的數據結構裡。
每位都只有0和1兩個值。為0的時候，證明值不存在，為1的時候說明存在。

舉例來說：

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

這是24位，也就是24bit, 同時8bit為1個字節。這裡的空間也就是3個字節。

這個時候假如我們要存放2 4 6 8 9 10 17 19 21這些數字到我們的BitMap裡，我們只用把對應的位設置為1就可以了。

[0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0]

這樣我們只用3個字節就存放了 9 * sizeof(int)大小的數字。在64位編譯器裡一般一個int類型是32bit也就是4個字節。我們存放這麼多數字，連一個int的空間都不到。

BitMap實現

其實BitMap實現不是很難，只是平時可能用位運算不是特別多。所以不熟悉。

主要的操作有三個，除了初始化之外，就是set() 和 get() 還有 del()方法，這三個，一個是把index置為1，一個是得到index位的0 or 1，最後的是把index位置位0.

下面是代碼實現：

//
//  Header.h
//  BloomFilter
//
//  Created by Alps on 15/3/19.
//  Copyright (c) 2015年 chen. All rights reserved.
//
//這個是 BitMap.h文件。

class BitMap{
public:
    BitMap(){
        bitmap = NULL;
        size = 0;
    }
    BitMap(int size){ // contractor, init the bitmap
        bitmap = NULL;
        bitmap = new char[size];
        if (bitmap == NULL) {
            printf("ErroR In BitMap Constractor!\n");
        }else{
            memset(bitmap, 0x0, size * sizeof(char));
            this->size = size;
        }
    }


    /*
     * set the index bit to 1;
     */
    int bitmapSet(int index){
        int addr = index/8;
        int addroffset = index%8;
        unsigned char temp = 0x1 << addroffset;
        if (addr > (size+1)) {
            return 0;
        }else{
            bitmap[addr] |= temp;
            return 1;
        }
    }

    /*
     * return if the index in bitmap is 1;
     */
    int bitmapGet(int index){
        int addr = index/8;
        int addroffset = index%8;
        unsigned char temp = 0x1 << addroffset;
        if (addr > (size + 1)) {
            return 0;
        }else{
            return (bitmap[addr] & temp) > 0 ? 1 : 0;
        }
    }

    /*
     * del the index from 1 to 0
     */
    int bitmapDel(int index){
        if (bitmapGet(index) == 0) {
            return 0;
        }
        int addr = index/8;
        int addroffset = index%8;
        unsigned char temp = 0x1 << addroffset;
        if (addr > (size + 1)) {
            return 0;
        }else{
            bitmap[addr] ^= temp;
            return 1;
        }
    }

private:
    char *bitmap;
    int size;
};

調用方法，大家應該都會。
代碼比較簡單，我下面的博客會寫Bloom Filter, 用到了這個BitMap。