數(shù)據(jù)結(jié)構(gòu)之位圖（bitmap）詳解

更新時(shí)間：2014年08月28日 10:14:21 投稿：junjie

這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之位圖詳解,本文講解了位圖的基本知識、位圖的實(shí)現(xiàn)方法、位圖的應(yīng)用等內(nèi)容,需要的朋友可以參考下

1. 概述

位圖（bitmap）是一種非常常用的結(jié)構(gòu)，在索引，數(shù)據(jù)壓縮等方面有廣泛應(yīng)用。本文介紹了位圖的實(shí)現(xiàn)方法及其應(yīng)用場景。

2. 位圖實(shí)現(xiàn)

（1）自己實(shí)現(xiàn)
在位圖中，每個元素為“0”或“1”，表示其對應(yīng)的元素不存在或者存在。

復(fù)制代碼代碼如下:

#define INT_BITS sizeof(int)

#define SHIFT 5 // 2^5=32

#define MASK 0x1f // 2^5=32

#define MAX 1024*1024*1024 //max number

int bitmap[MAX / INT_BITS];

/*

* 設(shè)置第i位

* i >> SHIFT 相當(dāng)于 i / (2 ^ SHIFT),

* i&MASK相當(dāng)于mod操作 m mod n 運(yùn)算

*/

void set(int i) {

bitmap[i >> SHIFT] |= 1 << (i & MASK);

}

//獲取第i位

int test(int i) {

return bitmap[i >> SHIFT] & (1 << (i & MASK));

}

//清除第i位

int clear(int i) {

return bitmap[i >> SHIFT] & ~(1 << (i & MASK));

}

（2）函數(shù)庫實(shí)現(xiàn)

C++的STL中有bitmap類，它提供了很多方法，詳見：http://www.cplusplus.com/reference/stl/bitset/

3. 位圖應(yīng)用

3.1 枚舉
（1）全組合
字符串全組合枚舉（對于長度為n的字符串，組合方式有2^n種），如：abcdef,可以構(gòu)造一個從字符串到二進(jìn)制的映射關(guān)系，通過枚舉二進(jìn)制來進(jìn)行全排序。

復(fù)制代碼代碼如下:

null——> 000000

f——> 000001

e——> 000010

ef——> 000011

……

abcedf——> 111111

（2）哈米爾頓距離

枚舉算法，復(fù)雜度是O(N^2)，怎樣降低復(fù)雜度呢？
如果是N 個二維的點(diǎn)，那么我們可以怎么用較快的方法求出

通過簡單的數(shù)學(xué)變形，我們可以得到這樣的數(shù)學(xué)公式：

通過觀察，我們發(fā)現(xiàn)每一對相同元的符號必定相反，如：x_i-y_i，于是我們有了一個二進(jìn)制思想的思路，那就是枚舉這些二i維的點(diǎn)的x 軸y 軸前的正負(fù)號，這樣就可以用一個0~3 的數(shù)的二進(jìn)制形式來表示每個元素前面的正負(fù)號，1表示+號，0表示−號，如：2 表示的二進(jìn)制位形式為10表示x_i-y_i。這樣我們就可以通過2^2*N次記錄下這些二元組的不同的符號的數(shù)值，對于每個二進(jìn)制來表示的不同的式子只需記錄下他們的值，這樣我們只需求max_i 和min_i出這些相同的二進(jìn)制表示的式子max_i –min_i，最后我們就可以解出ans=max{max_i-min_i}。

通過位圖，算法時(shí)間復(fù)雜度可將為O(N)。

3.2 搜索

設(shè)計(jì)搜索剪枝時(shí)，需要保存已經(jīng)搜索過的歷史信息，有些情況下，可以使用位圖減小歷史信息數(shù)據(jù)所占空間。

3.3 壓縮

（1）在2.5億個整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這2.5億個整數(shù)？

（2）騰訊面試題：給40億個不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中？

4. 總結(jié)

Bitmap是一種非常簡潔快速的數(shù)據(jù)結(jié)構(gòu)，他能同使證存儲空間和速度最優(yōu)化（而不必空間換時(shí)間）。

5. 參考資料
（1）《C實(shí)現(xiàn)bitmap位圖》：http://www.dbjr.com.cn/article/54438.htm
（2）武森《淺談信息學(xué)競賽中的“0”和“1”》

您可能感興趣的文章: