bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

位图法

bitmap

bitmap

判断某个数据存不存在

大规模数据，数据状态又不多

举例

例如，要判断一千万个人的状态，每个人只有两种状态：男人，女人，可以用0，1表示。那么就可以开一个int数组，一个int有32个位，就可以表示32个人。操作的时候可以使用位操作。[1]

应用

一、给40亿个不重复的unsignedint的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

申请512M的内存

一个bit位代表一个unsignedint值

读入40亿个数，设置相应的bit位

读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在

二、使用位图法判断整形数组是否存在重复

判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。

位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

示例代码如下：

packagecom.sitinspring;

publicclassDuplicatedArrayTest{

publicstaticvoidmain(String[]args){

int[][]arr={

{1,2,3,5,3,5,56,534,3,32},

{1,2,3,5},

{1,2,3,5,3,5},

{0,0,1,2,3,5,56,534,78,32},

};

for(inti=0;i<arr.length;i++){

System.out.print("数组:");

for(inttemp:arr[i]){

System.out.print(temp+",");

}

System.out.print("中");

System.out.print(hasDuplicatedItem(arr[i])?"存在":"不存在");

System.out.print("重复元素. ");

}

}

/**

*判断整形数组中是否有重复数据，时间复杂度为O（n）

*@paramarr

*@return

*/

publicstaticbooleanhasDuplicatedItem(int[]arr){

//扫描数组找最大值

intmax=arr[0];

for(inti=1;i<arr.length;i++){

if(arr[i]>max){

max=arr[i];

}

}

//按最大值创建一个新数组

int[]bitArray=newint[max+1];

//按值向新数组中添值，如value为3则bitArray[3]=1

for(intvalue:arr){

if(bitArray[value]!=0){

//如果value指向的位置已经不是零，说明之前已经给这一块置1了，立即返回true表示数组有重复

returntrue;

}

else{

//value指向的位置是零,则置为1表示这一位已经有数存在了

bitArray[value]=1;

}

}

returnfalse;

}

}

输出：

数组:1,2,3,5,3,5,56,534,3,32,中存在重复元素.

数组:1,2,3,5,中不存在重复元素.

数组:1,2,3,5,3,5,中存在重复元素.

数组:0,0,1,2,3,5,56,534,78,32,中存在重复元素.

三、使用位图法进行整形数组排序

packagecom.heyang;

publicclassBitmapSorter{

publicstaticvoidmain(String[]args){

int[]arr={1,7,-3,0,0,6,6,9,-11};

bitmapSort(arr);

for(inti:arr){

System.out.print(i+",");

}

}

/**

*使用位图法进行排序

*@paramarr

*/

publicstaticvoidbitmapSort(int[]arr){

//找出数组中最值

intmax=arr[0];

intmin=max;

for(inti:arr){

if(max<i){

max=i;

}

if(min>i){

min=i;

}

}

//得到位图数组

int[]newArr=newint[max-min+1];

for(inti:arr){

intindex=i-min;

newArr[index]++;

}

//重整arr中的元素

intindex=0;

for(inti=0;i

while(newArr[i]>0){

arr[index]=i+min;

index++;

newArr[i]--;

}

}

}

}

四、位图法存数据

在8K字节的内存空间内，如何存unsignedshort类型数据？

一般做法：

定义一个数组：unsignedshortarrNormal[4096];

这样做，最多只能存4K个unsignedshort数据。

利用位图法：

定义一个数组：unsignedchararrBit[8192];

这样做，能存8K*8=64K个unsignedshort数据。

rrBit存放的字节位置和位位置（字节0~8191，位0~7）

比如写1234，字节序：1234/8=154;位序：1234&0b111=2，那么1234放在arrBit的下标154字节处，把该字节的2号位（0~7）置为1

字节位置：intnBytePos=1234/8=154;

位位置：intnBitPos=1234&7=2;

//把数组的154字节的2位置为1

unsignedshortval=1<

arrBit[nBytePos]=arrBit[nBytePos]|val;//写入1234得到arrBit[154]=0b00000100

此时再写入1236，

字节位置：intnBytePos=1236/8=154;

位位置：intnBitPos=1236&7=4

.///把数组的154字节的4位置为1

val=1<

arrBit[nBytePos]=arrBit[nBytePos]|val;//再写入1236得到arrBit[154]=0b00010100

读数据元素：按位读取arrBit，取得位为1的字节位置和位位置。元素值为8*nBytePos+nBitPos

for(i=0;i<8192;i++)

{

for(j=0;j<8;j++)

{

if(arrBit[i]&(1<

{

cout<<"arrBit:"<<i<<""<<j<<""<<8*i+j<

}

}

}

会输出：

arrBit:15421234

arrBit:15441236

删除元素：计算待删除元素的字节位置和位位置：arrBit[nBytePos]&=~(1<<nBitPos);

比如删除1234：arrBit[154]&=~(1<<2);