1. Bit Map算法簡介

? ? ? ?? 來自于《編程珠璣》。所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。

2、 Bit Map的基本思想

? ? ? ? 我們先來看一個具體的例子，假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。那么我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，如下圖：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

然后遍歷這5個元素，首先第一個元素是4，那么就把4對應的位置為1（可以這樣操作 p+(i/8)|(0x01<<(i%8)) 當然了這里的操作涉及到Big-ending和Little-ending的情況，這里默認為Big-ending）,因為是從零開始的，所以要把第五位置為一（如下圖）：
?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

然后再處理第二個元素7，將第八位置為1,，接著再處理第三個元素，一直到最后處理完所有的元素，將相應的位置為1，這時候的內存的Bit位的狀態如下：?
?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

然后我們現在遍歷一遍Bit區域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。

優點：

1.運算效率高，不許進行比較和移位；

2.占用內存少，比如N=10000000；只需占用內存為N/8=1250000Byte=1.25M。?
缺點：

? ? ? ?所有的數據不能重復。即不可對重復的數據進行排序和查找。 ? ?

算法思想比較簡單，但關鍵是如何確定十進制的數映射到二進制bit位的map圖。

3、 Map映射表

假設需要排序或者查找的總數N=10000000，那么我們需要申請內存空間的大小為int a[1 + N/32]，其中：a[0]在內存中占32為可以對應十進制數0-31，依次類推：?
bitmap表為：?
a[0]--------->0-31?
a[1]--------->32-63?
a[2]--------->64-95?
a[3]--------->96-127?
..........?
那么十進制數如何轉換為對應的bit位，下面介紹用位移將十進制數轉換為對應的bit位。?

3、 位移轉換?

申請一個int一維數組，那么可以當作為列為32位的二維數組，

?????????????? |???????????????????????????32位??????????????????????? ? ? ? ? ? ? ?? |

int a[0]??? |0000000000000000000000000000000000000|

int a[1]??? |0000000000000000000000000000000000000|

………………

int a[N]?? |0000000000000000000000000000000000000|

例如十進制0，對應在a[0]所占的bit為中的第一位：?00000000000000000000000000000001?
0-31：對應在a[0]中?
i =0 ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000000?
temp=0 ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000000000?
answer=1 ? ? ? ? ? ? ? ? 00000000000000000000000000000001?

i =1 ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000001?
temp=1 ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000000001?
answer=2 ? ? ? ? ? ? ? ? 00000000000000000000000000000010?

i =2 ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000010?
temp=2 ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000000010?
answer=4 ? ? ? ? ? ? ? ? 00000000000000000000000000000100?

i =30 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000011110?
temp=30 ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000011110?

answer=1073741824??01000000000000000000000000000000?

i =31 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000011111?
temp=31 ? ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000011111?
answer=-2147483648?10000000000000000000000000000000?

32-63：對應在a[1]中?
i =32 ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000100000?
temp=0 ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000000?
answer=1 ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000001?

i =33 ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000100001?
temp=1 ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000000001?
answer=2 ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000010?

i =34 ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000100010?
temp=2 ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000010?
answer=4 ? ? ? ? ? ? ? ? ? ?00000000000000000000000000000100?

i =61 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000111101?
temp=29 ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000011101?
answer=536870912?? ?00100000000000000000000000000000?

i =62 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000111110?
temp=30 ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000011110?
answer=1073741824??01000000000000000000000000000000?

i =63 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000000000000000000000111111?
temp=31 ? ? ? ? ? ? ? ? ? ? ? ? 00000000000000000000000000011111?
answer=-2147483648??10000000000000000000000000000000

淺析上面的對應表，分三步：?
1.求十進制0-N對應在數組a中的下標：?
十進制0-31，對應在a[0]中，先由十進制數n轉換為與32的余可轉化為對應在數組a中的下標。比如n=24,那么 n/32=0，則24對應在數組a中的下標為0。又比如n=60,那么n/32=1，則60對應在數組a中的下標為1，同理可以計算0-N在數組a中的下標。?

2.求0-N對應0-31中的數：?

十進制0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得對應0-31中的數。?

3.利用移位0-31使得對應32bit位為1.?

找到對應0-31的數為M, 左移M位：即2^M. 然后置1.

由此我們計算10000000個bit占用的空間：

1byte =?8bit

1kb =?1024byte

1mb =?1024kb

占用的空間為：10000000/8/1024/1024mb。

大概為1mb多一些。

3、 擴展?

??????? Bloom filter可以看做是對bit-map的擴展?

4、 Bit-Map的應用

? ? ??1）可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下。

?????? 2）去重數據而達到壓縮數據

5、 Bit-Map的具體實現

c語言實現：

[cpp]?view plaincopyprint?

#define?BITSPERWORD?32??

#define?SHIFT?5??

#define?MASK?0x1F??

#define?N?10000000??

??

int?a[1?+?N/BITSPERWORD];//申請內存的大小??

??

??

//set?設置所在的bit位為1??

void?set(int?i)?{??????????

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

}??

//clr?初始化所有的bit位為0??

void?clr(int?i)?{??????????

????a[i>>SHIFT]?&=?~(1<<(i?&?MASK));???

}??

//test?測試所在的bit為是否為1??

int??test(int?i){???

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

}??

??

int?main()??

{???int?i;??

????for?(i?=?0;?i?<?N;?i++)??

????????clr(i);????

????while?(scanf("%d",?&i)?!=?EOF)??

????????set(i);??

????for?(i?=?0;?i?<?N;?i++)??

????????if?(test(i))??

????????????printf("%d\n",?i);??

????return?0;??

}??

注明： 左移n位就是乘以2的n次方，右移n位就是除以2的n次方

解析本例中的void set(int i) {??????? a[i>>SHIFT] |=? (1<<(i & MASK)); }
1) ?i>>SHIFT：?
其中SHIFT=5，即i右移5為，2^5=32,相當于i/32，即求出十進制i對應在數組a中的下標。比如i=20，通過i>>SHIFT=20>>5=0 可求得i=20的下標為0；

2) ?i & MASK：?
其中MASK=0X1F,十六進制轉化為十進制為31，二進制為0001 1111，i&（0001 1111）相當于保留i的后5位。?

比如i=23，二進制為：0001 0111，那么?
???????????????????????? 0001 0111?
?????????????????? &??? 0001 1111 = 0001 0111 十進制為：23?
比如i=83，二進制為：0000 0000 0101 0011，那么?
????????????????????????? 0000 0000 0101 0011?
???????????????????? &?? 0000 0000 0001 0000 = 0000 0000 0001 0011 十進制為：19?

i & MASK相當于i%32。?

3) 1<<(i & MASK)?
相當于把1左移 (i & MASK)位。?
比如(i & MASK)=20，那么i<<20就相當于：?
???????? 0000 0000 0000 0000 0000 0000 0000 0001 << 20?
? ? ? ?=0000 0000 0001?0000 0000 0000 0000 0000?

注意上面 “|=”.

在博文：位運算符及其應用?提到過這樣位運算應用：

?將int型變量a的第k位清0，即a=a&~(1<<k)
?將int型變量a的第k位置1， 即a=a|(1<<k)

這里的將 ?a[i/32] |= (1<<M));?第M位置1 .

4) void set(int i) {??????? a[i>>SHIFT] ?|=? (1<<(i & MASK)); }等價于：
[cpp]?view plaincopyprint?

void?set(int?i)???

{???

???a[i/32]?|=?(1<<(i%32));???

}??

即實現上面提到的三步：

1.求十進制0-N對應在數組a中的下標：?n/32?

2.求0-N對應0-31中的數： N%32=M

3.利用移位0-31使得對應32bit位為1: 1<<M，并置1;

php實現是一樣的：

[cpp]?view plaincopyprint?

<?php????

??error_reporting(E_ERROR);??

define("MASK",?0x1f);//31????

define("BITSPERWORD",32);?????

define("SHIFT",5);????

define("MASK",0x1F);???

define("N",1000);???

??

?$a?=?array();???

//set?設置所在的bit位為1????

function?set($i)?{?????

????global?$a;?????????

????$a[$i>>SHIFT]?|=??(1<<($i?&?MASK));?????

}????

//clr?初始化所有的bit位為0????

function?clr($i)?{????????????

????$a[$i>>SHIFT]?&=?~(1<<($i?&?MASK));?????

}????

//test?測試所在的bit為是否為1????

function?test($i){????

????global?$a;????

????return?$a[$i>>SHIFT]?&?(1<<($i?&?MASK));?????

}????

$aa?=?array(1,2,3,31,?33,56,199,30,50);????

while?($v?=current($aa))??{??

???set($v);???

???if(!next($aa))?{??

???????break;??

???}??

}??

foreach?($a?as?$key=>$v){??

????echo?$key,'=',?decbin($v),"\r\n";??

}??

然后我們打印結果：

0=11000000000000000000000000001110
1=1000001000000000000000010
6=10000000

32位表示，實際結果一目了然了，看看1,2,3,30,31, 33,50，56,199數據所在的具體位置：

? ? ? ?31 ? ?30 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3 ? ? 2 ? ? 1

? ? ? ?????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??????

0= ? ?1 ? ? 1 ? ?00 ? ? ? 0000 ? 0000 ? 0000 ? 0000 ? ?0000 ? ? 0000 ? 1 ? ? 1 ? 1 ?0

? ? ? ? ? ? ? ? ? ? ? ? ??56 ? ? ? ? ? ? ? ? 50 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?33

? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????
1= ?0000 ? ? 0001 ? ?0000 ? 0100 ? 0000 ? ?0000 ? ? 0000 ? ?0010

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ?199

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???
6= ?0000 ?0000 ? ?0000 ? 0000 ? 0000 ? ?0000 ? ?1000 ? ?0000

【問題實例】

已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。 （可以理解為從0-99 999 999的數字，每個數字對應一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內存表示了所有的8位數的電話）


2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。?
將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上，在遍歷這些數的時候，如果對應位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變?；蛘呶覀儾挥?bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map，都是一樣的道理。

實現：

[cpp]?view plaincopyprint?

//?TestWin32.cpp?:?Defines?the?entry?point?for?the?console?application.??

#include?"stdafx.h"??

??

#include<memory.h>????

??

//用char數組存儲2-Bitmap,不用考慮大小端內存的問題????

unsigned?char?flags[1000];?//數組大小自定義?????

unsigned?get_val(int?idx)??{???

//??|????8?bit??|??

//??|00?00?00?00|??//映射3?2?1?0??

//??|00?00?00?00|??//表示7?6?5?4??

//??……??

//??|00?00?00?00|??

??

????int?i?=?idx/4;??//一個char?表示4個數，??

????int?j?=?idx%4;????

????unsigned?ret?=?(flags[i]&(0x3<<(2*j)))>>(2*j);????

????//0x3是0011?j的范圍為0-3，因此0x3<<(2*j)范圍為00000011到11000000?如idx=7?i=1?,j=3?那么flags[1]&11000000,?得到的是|00?00?00?00|??

????//表示7?6?5?4??

???return?ret;????

}????

????????

unsigned?set_val(int?idx,?unsigned?int?val)??{????

????int?i?=?idx/4;????

????int?j?=?idx%4;????

????unsigned?tmp?=?(flags[i]&~((0x3<<(2*j))&0xff))?|?(((val%4)<<(2*j))&0xff);????

????flags[i]?=?tmp;????

????return?0;????

}????

unsigned?add_one(int?idx)????

{????

????if?(get_val(idx)>=2)?{??//這一位置上已經出現過了？？??

????????return?1;????

????}??else??{????

????????set_val(idx,?get_val(idx)+1);????

????????return?0;????

????}????

}????

????????

//只測試非負數的情況;????

//假如考慮負數的話,需增加一個2-Bitmap數組.????

int?a[]={1,?3,?5,?7,?9,?1,?3,?5,?7,?1,?3,?5,1,?3,?1,10,2,4,6,8,0};????

????????

int?main()???{????

????int?i;????

????memset(flags,?0,?sizeof(flags));????

????????????

????printf("原數組為:");????

????for(i=0;i?<?sizeof(a)/sizeof(int);?++i)??{????

????????printf("%d??",?a[i]);????

????????add_one(a[i]);????

????}????

????printf("\r\n");????

????????

????printf("只出現過一次的數:");????

????for(i=0;i?<?100;?++i)??{????

????????if(get_val(i)?==?1)????

????????????printf("%d??",?i);????

????????}????

????printf("\r\n");????

??????

????return?0;????

} ?

?// from:?http://blog.csdn.net/hguisu/article/details/7880288

總結

以上是生活随笔為你收集整理的海量数据处理算法—Bit-Map的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。