Bitset位图

位图(bitmap)就是用每一位来存放某种状态，适合于大规模数据但是数据状态又不是很多的情况下，通常来判断数据是否存在。位图的常见应用有两种：

1.存放大规模数据，例如腾讯的面试题，给40亿个unsigned int的整数。给一个无符号的整数，融合判断这个数是否在这40亿个整数中。一个bit位代表一个unsigned int值，读入40 亿个数设置相应的bit位，为1表示存在，为0表示不存在。

2.用位图法来判定一个数组是否存在重复。它的做法是：按照集合中最大元素max创建一个长度为max+1的数组，扫描该数组，遇到几就给该数组的第几位+1置1，如果遇到某位已经是1了，则表示该位减一的数据存在重复。

其代码实现如下：

#pragma once
#include<vector>

class BitMap
{
public:
BitMap()
:_size(0)
{}

BitMap(size_t n)
:_size(0)
{
_array.resize((n >> 5) + 1);//无符号整形是八个字节32个比特位
}

bool Test(size_t num)//查看此数是否存在
{
size_t index = num>>5;
size_t n = num % 32;
return _array[index]&(1 << n);
}

bool set(size_t num)
{
size_t index = num >> 5;
size_t n = num % 32;
if (_array[index] & (1 << n))
{
return false;
}

_array[index] |= 1 << n;//注意这里，右移是向其高位移动，并不是真的向右移动
_size++;
return true;
}

bool reset(size_t num)
{
size_t index = num >> 5;

size_t n=num%32;

if(！_array[index]&(1<<n);
{
return false;
}
_array[index] &= ~(1 << n);
_size--;
return true;
}

void clear()
{
_array.assign(_array.size(), 0);
}

protected:
vector<size_t> _array;
size_t _size;
};

void test()
{
BitMap bm1(100);
bm1.set(1);
bm1.set(33);
bm1.set(69);
bm1.set(100);

bm1.reset(33);
}

巴特西