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);
}

上一篇:Spring 4 官方文档学习(十一)Web MVC 框架之HTTP caching support


下一篇:【bzoj1502】[NOI2005]月下柠檬树 自适应Simpson积分