BitMap
前言
Bitmap的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
原理
bitmap就是使用bit位的值0或1标识一个数是否存在,0表示存在,1则表示不存在
如何使用bitmap表示一个数?
根据上述的实现原理可知,每一位表示一个数,0表示不存在,1表示存在。例如:{1,2,4,6}这几个数怎么在bitmap中表示?
计算机内存分配的最小单位是字节,也就是8位,那如果要表示{12,13,15}怎么办呢?当然是在另一个8位上表示了:
1个int占32位,那么只需要申请一个int数组长度为 int tmp[1+N/32] 即可存储,其中N表示要存储的这些数中的最大值,于是乎:
tmp[0]:可以表示0-31
tmp[1]:可以表示32-63
tmp[2]:可以表示64~95
给定任意整数M,那么M/32就得到下标,M%32就知道它在此下标的哪个位置
bitmap操作
添加元素
怎么把一个数添加到bitmap中呢?例如,想把5这个数字添加到bitmap?
首先,5/32=0,5%32=5,也是说它应该在tmp[0]的第5个位置,那我们把1向左移动5位,然后按位或:
相当于:86 | (1