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ù)庫(kù)實(shí)現(xiàn)

C++的STL中有bitmap類(lèi)，它提供了很多方法，詳見(jiàn)：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)系，通過(guò)枚舉二進(jìn)制來(lái)進(jìn)行全排序。

（2）哈米爾頓距離

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

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

通過(guò)觀察，我們發(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)制形式來(lái)表示每個(gè)元素前面的正負(fù)號(hào)，1表示+號(hào)，0表示−號(hào)，如：2 表示的二進(jìn)制位形式為10表示x_i-y_i。這樣我們就可以通過(guò)2^2*N次記錄下這些二元組的不同的符號(hào)的數(shù)值，對(duì)于每個(gè)二進(jìn)制來(lái)表示的不同的式子只需記錄下他們的值，這樣我們只需求max_i 和min_i出這些相同的二進(jìn)制表示的式子max_i