BitMap（位图）结构的C++实现

简介

位图是一种非常常见的结构，它使用每个二进制位来存放一个值的状态，正因为这个性质，它经常被用在数据压缩或者是索引等方面。

有这样一道题：给40亿个不重复的无符号整数，没有经过排序，然后再给一个树，如何快速判断这个数是否在40亿个数之中？

在这里如果我们实打实的存放40亿个数据在内存中，那会占据将近15个G的内存，普通电脑根本无法满足，更不用说在对其进行查找操作了。 那么如果选择位图来存储的话我们只需要差不多500M就够了。大大的节省了内存的消耗。

如下图，我们把1状态设为存在状态，0状态设为不存在，那么该组数据中就存在2和5。

位图的操作

在我设计的BitMap里给出了三个接口

1.Set：用来把x位置的状态位置一，表示x已存在； 实现原理是将要存入的数据除以32得到他的所在字节，然后再对要存入的数据模32，得到他在这个字节的位。再把“1”状态移动到这个位。

void Set(size_t x) {//将x位置的状态置一 if (x / 32 > _v.size()) { cout << "参数" << x << "超出范围" << endl; return; } size_t index = x >> 5; size_t num = x % 32; _v[index] |= 1 << (num - 1); }

2.Reset：重新把x位置的状态置零； 实现原理和Set的基本一样，但是最后因为是置零所以我们采用了异或的方法，把x的状态位清零。

void Reset(size_t x) {//将x位置的状态的置零 if (x / 32 > _v.size()) { cout << "参数" << x << "超出范围" << endl; return; } size_t index = x >> 5; size_t num = x % 32; _v[index] ^= 1 << (num - 1); }

3.Find：查找x位置的状态。 查找的实现原理前两步和上面一样，先找到x的所在的位位置，然后通过位移操作取出这个位，再和1做与得并返回。

int Find(size_t x) {//查找x位置的状态并返回 if (x/32 > _v.size()) { cout << "参数"<<x<<"超出范围" << endl; return false; } size_t index = x >> 5; size_t num = x % 32; return (_v[index] >> (num - 1)) & 1; }

在这三个接口里，我都加入了参数检测，是为了防止给入的参数超过位图所能存储的范围。

代码实现

#pragma once #include<iostream> #include<vector> using namespace std; /* *Authotr:Seven17000 *Date:2017.03.12 *Content:实现位图 */ class BitMap { public: BitMap(size_t size = 100) {//构造函数 //size为要处理的的数据总数 //一个整型可以存放32个数据状态 //所以这里vector的size为size/32 _v.resize((size >> 5) + 1); } void Set(size_t x) {//将x位置的状态置一 if (x / 32 > _v.size()) { cout << "参数" << x << "超出范围" << endl; return; } size_t index = x >> 5; size_t num = x % 32; _v[index] |= 1 << (num - 1); } void Reset(size_t x) {//将x位置的状态的置零 if (x / 32 > _v.size()) { cout << "参数" << x << "超出范围" << endl; return; } size_t index = x >> 5; size_t num = x % 32; _v[index] ^= 1 << (num - 1); } int Find(size_t x) {//查找x位置的状态并返回 if (x/32 > _v.size()) { cout << "参数"<<x<<"超出范围" << endl; return false; } size_t index = x >> 5; size_t num = x % 32; return (_v[index] >> (num - 1)) & 1; } private: vector<size_t> _v; };