1.  概述

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

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

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

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

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

3.  位圖應(yīng)用

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

（2）哈米爾頓距離

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

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

通過觀察，我們發(fā)現(xiàn)每一對(duì)相同元的符號(hào)必定相反，如：x_i-y_i，于是我們有了一個(gè)二進(jìn)制思想的思路，那就是枚舉這些二i維的點(diǎn)的x 軸y 軸前的正負(fù)號(hào)，這樣就可以用一個(gè)0~3 的數(shù)的二進(jìn)制形式來表示每個(gè)元素前面的正負(fù)號(hào)，1表示+號(hào)，0表示−號(hào)，如：2 表示的二進(jìn)制位形式為10表示x_i-y_i。這樣我們就可以通過2^2*N次記錄下這些二元組的不同的符號(hào)的數(shù)值，對(duì)于每個(gè)二進(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億個(gè)整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這2.5億個(gè)整數(shù)？

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

4. 總結(jié)

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

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