數據構造之位圖（bitmap）詳解。本站提示廣大學習愛好者：（數據構造之位圖（bitmap）詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是數據構造之位圖（bitmap）詳解正文
1. 概述
位圖（bitmap）是一種異常經常使用的構造，在索引，數據緊縮等方面有普遍運用。本文引見了位圖的完成辦法及其運用場景。
2. 位圖完成
（1）本身完成
在位圖中，每一個元素為“0”或“1”，表現其對應的元素不存在或許存在。
#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];
/*
* 設置第i位
* i >> SHIFT 相當於 i / (2 ^ SHIFT),
* i&MASK相當於mod操作 m mod 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）函數庫完成
C++的STL中有bitmap類，它供給了許多辦法，詳見：http://www.cplusplus.com/reference/stl/bitset/
3. 位圖運用
3.1 列舉
（1）全組合
字符串全組合列舉（關於長度為n的字符串，組合方法有2^n種），如：abcdef,可以結構一個從字符串到二進制的映照關系，經由過程列舉二進制來停止全排序。
null——> 000000
f——> 000001
e——> 000010
ef——> 000011
……
abcedf——> 111111
（2）哈米爾頓間隔
列舉算法，龐雜度是O(N^2)，如何下降龐雜度呢？
假如是N 個二維的點，那末我們可以怎樣用較快的辦法求出
經由過程簡略的數學變形，我們可以獲得如許的數學公式：
經由過程不雅察，我們發明每對雷同元的符號一定相反，如：x_i-y_i，因而我們有了一個二進制思惟的思緒，那就是列舉這些二i維的點的x 軸y 軸前的正負號，如許便可以用一個0~3 的數的二進制情勢來表現每一個元素後面的正負號，1表現+號，0表現−號，如：2 表現的二進制位情勢為10表現x_i-y_i。如許我們便可以經由過程2^2*N次記載下這些二元組的分歧的符號的數值，關於每一個二進制來表現的分歧的式子只需記載下他們的值，如許我們只需求max_i 和min_i出這些雷同的二進制表現的式子max_i –min_i，最初我們便可以解出ans=max{max_i-min_i}。
經由過程位圖，算法時光龐雜度可將為O(N)。
3.2 搜刮
設計搜刮剪枝時，須要保留曾經搜刮過的汗青信息，有些情形下，可使用位圖減小汗青信息數據所占空間。
3.3 緊縮
（1）在2.5億個整數中找出不反復的整數，注，內存缺乏以包容這2.5億個整數？
（2）騰訊面試題：給40億個不反復的unsigned int的整數，沒排過序的，然後再給一個數，若何疾速斷定這個數能否在那40億個數傍邊？
4. 總結
Bitmap是一種異常簡練疾速的數據構造，他能同使證存儲空間和速度最優化（而不用空間換時光）。
5. 參考材料
（1）《C完成bitmap位圖》：http://www.jb51.net/article/54438.htm
（2）武森《淺談信息學比賽中的“0”和“1”》
