算法學習 - 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 = ;
    }
    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, , size * sizeof(char));
            this->size = size;
        }
    }


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

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

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

private:
    char *bitmap;
    int size;
};
           

調用方法，大家應該都會。

代碼比較簡單，我下面的部落格會寫Bloom Filter, 用到了這個BitMap。