郑州建设银行网站,重庆九度设计,哈尔滨专业的建站报价,seo推广思路BitMap 位图#xff08;bitmap#xff09;是一种非常常用的结构#xff0c;在索引#xff0c;数据压缩等方面有广泛应用。位图是通过将数组下标与应用中的一些值关联映射#xff0c;数组中该下标所指定的位置上的元素可以用来标识应用中值的情况#xff08;是否存在或者数…BitMap 位图bitmap是一种非常常用的结构在索引数据压缩等方面有广泛应用。位图是通过将数组下标与应用中的一些值关联映射数组中该下标所指定的位置上的元素可以用来标识应用中值的情况是否存在或者数目 或者计数等位图数组中每个元素在内存中占用1位所以可以节省存储空间。位图是一种非常简洁快速的数据结构它能同时使存储空间和速度最优化。如可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合例如可以用如下字符串表示集合{1,2,4,5,8} 对应位置数字存在标记为1否则标记为0。 这里BitMap指的是把数据存放在一个以bit为单位的数据结构里。 每位都只有0和1两个值。为0的时候证明值不存在为1的时候说明存在。
举例来说
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]这是24位也就是24bit, 同时8bit为1个字节。这里的空间也就是3个字节。
这个时候假如我们要存放2 4 6 8 9 10 17 19 21这些数字到我们的BitMap里我们只需把对应的位设置为1就可以了。
[0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0]数据结构
假如我们要存储的数据范围为0-15这里的数据是16bit:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]数据为[5, 1, 7, 15, 0, 4, 6, 10]
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
[1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1]例如
申请一个int型的内存空间则有4Byte32bit。输入 4 2, 1, 3时
输入4
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
输入2
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]
输入1
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0]
输入3
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0]
map映射表
假设需要排序或者查找的总数N10000000,那么我们需要申请的内存空间为 int a[N/32 1].其中a[0]在内存中占32位,依此类推
bitmap表为
a[0] —— 0 - 31
a[1] —— 32 - 63
a[2] —— 64 - 95
a[3] —— 96 - 127
……
位移转换
求十进制数0-N对应的在数组a中的下标 公式index N / 32即可index即为对应的数组下标。例如N 76, 则index 76 / 32 2,因此76在a[2]中。求十进制数0-N对应的bit位 bit N % 32即可例如 N 76, bit 76 % 32 12利用移位0-31使得对应的32bit位为1
代码实现
##include iostream
#include vectorusing namespace std;class BitMap
{
public:BitMap( int range ){//开辟空间this-m_bits.resize(range / 32 1);}void set( int data ){int index data / 32; //数组索引即区间int temp data % 32; //具体位置索引this-m_bits[index] | ( 1 temp); //左移4位置为1}void reset( int data){int index data / 32;int temp data % 32;this-m_bits[index] ~( 1 temp ); //取反}bool test(int data){int index data / 32;int temp data % 32;if( this-m_bits[index]( 1 temp)){return true;}else{return false;}}private:vectorint m_bits;
};void testBitMap()
{BitMap bitmap_1(-1);BitMap bitmap_2(31);bitmap_2.set(16);bitmap_2.set(1);cout bitmap_2.test(16) endl;bitmap_2.reset(16);cout bitmap_2.test(16) endl;
}int main()
{testBitMap();
}
