当前位置：首页 > news >繁体>C++ 简易位图

C++ 简易位图

news 来源：原创 2023/3/22 5:43:59

前言

位图没啥好说的，实际上就是将一个数组中所有二进制位拆分出来，一个bit表示一个bool量主要使用的还是位运算来做，非常简单，一看就会

一、整体思路

根据用户需要使用的位图空间，申请一个适量大小的数组；
按位获取或设置每个bit位上的数据即可

二、几个易错步骤

1.初始化时

方便起见我将所有类型全设置为了无符号长整型；
用户传入需要的bit总长度，此时需计算需要创建的数组大小；

首先计算类型的bit长度：
$typeSz=类型占用字节数∗8\ typeSz = 类型占用字节数 * 8$
接着进行一个向上取整的除法运算，在这里表示为：余数不为0则多申请一个数据空间

mapSz = len / typeSz + (len % typeSz ? 1 : 0);

此时mapSz就是需要申请的数组大小。
接着申请内存并初始化为0即可。

2.设置位置时

先找到目标位置
使用位运算或将目标位置设置为1即可。

arr[index / typeSz] |= (1 << (index % typeSz));

3.获取位置时

同样也是找到目标位置；
判断该位置是否是1即可。

(arr[index / typeSz] >> (index % typeSz)) & 1;

三、完整代码

#include <iostream>
#include <cassert>
using namespace std;class BitMap
{typedef unsigned long T;T typeSz;T* arr = nullptr;		//位图数组T mapSz;	//数组大小T bitLen;	//总长度//初始化void init(T len){bitLen = len;typeSz = sizeof(T) * 8;mapSz = len / typeSz + (len % typeSz ? 1 : 0);if (arr != nullptr) delete arr;arr = new T[mapSz];for (size_t i = 0; i < mapSz; ++i)arr[i] = 0;}public://析构函数~BitMap(){if (arr != nullptr) delete arr;arr = nullptr;}//构造函数BitMap(T len){init(len);}//重置位图void reset(T len){init(len);}//设置位置void set(T index){assert(index < bitLen);arr[index / typeSz] |= (1 << (index % typeSz));}//获取位置bool get(T index){assert(index < bitLen);return (arr[index / typeSz] >> (index % typeSz)) & 1;}//数组方式获取位置bool operator[] (T index){return get(index);}
};