C# · 12月 20, 2021

十二、C++实现位图(bitmap)

一、定义                                                                                               –概念部分参考http://www.iteblog.com/archives/148

位图法就是bitmap的缩写。所谓bitmap,就是用每一位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器,其实就是位图法。

引用bitset介绍:A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false,…).The class is very similar to a regular array,but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).Each element (each bit) can be accessed individually: for example,for a given bitset named mybitset,the expression mybitset[3] accesses its fourth bit,just like a regular array accesses its elements.

二、数据结构

内部维护数组   char M [N];

在这个数组里面,可以存储 N * 8个数据,但是最大的数只能是N * 8 – 1。假如,我们要存储的数据范围为0-15,则我们只需要使得N=1,这样就可以把数据存进去。如下图:

数据为【5,1,7,15,0,4,6,10】,则存入这个结构中的情况为 

三、相关操作

对于内部数组 char M [8 * 1024]; 这样做,能存 8K*8=64K 个 bit。存放的字节位置和位位置(字节 0~8191 ,位 0~7 )。

内部实现均采用位操作,比如将第1234个位置1 ,字节序:1234 >> 3 = 154; 位序:0x80 >> (1234 & 0x07) = 2 ,那么 1234 放在 M 的下标 154 字节处,把该字节的 2 号位( 0~7)置为 1。

1. 置位(设操作第k个位) 

M[k >> 3] |= (0x80 >> (k & 0x07));

解释:M[第k个标志位所在的字节(k/8 取整)] |= (第k个标志位在所在字节中的位数(取余)) 

2. 复位(设操作第k个位)

M[k >> 3] &= ~(0x80 >> (k & 0x07));

解释:M[第k个标志位所在的字节(k/8 取整)] &= ~(第k个标志位在所在字节中的位数(取余))

3. 访问(设操作第k个位)

return M[k >> 3] & (0x80 >> (k & 0x07));

解释:M[第k个标志位所在的字节(k/8 取整)] &(第k个标志位在所在字节中的位的值)

4. 扩容

若被访问的M[k]已出界,则需扩容,与vector扩容原理类似,重新分配内存,容量加倍,并将原数据转移至新的空间。

四、位图的应用举例 (大规模数据,整数)

(1) 给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中。

40亿是个巨大的数量,如果将40亿个int变量完全存储到内存中可不得了,所以最好采用40亿个位(476M空间)来存放这40亿个数据的状态比较好。 

首先,遍历这40亿个数字,分别在对应的位图中进行置位。然后对于给出的数,进行按秩查找,判断是否在bitmap中即可。

(2) 使用位图法判断整形数组是否存在重复

遍历数组,以数组元素为秩,分别将bitmap中对应的位置1,并且检查其是否已经为1,若为1,即为重复的元素。      

(3) 使用位图法进行整形数组排序      

首先遍历数组,得到数组的最大最小值,然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数,都要转化为unsigned int来处理,而且取位的时候,数字要减去最小值。      

(4) 在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数

参考的一个方法是:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)。其实,这里可以使用两个普通的Bitmap,即第一个Bitmap存储的是整数是否出现,如果再次出现,则在第二个Bitmap中设置即可。这样的话,就可以使用简单的1-Bitmap了。

五、位图实现

实现位图并封装在bitmap类中。

bitmap接口列表

操作

功能

对象

bitmap(int n = 8)

构造函数,默认容量为8位

位图

bitmap(char* file,int n = 8)

构造函数,从指定文件中读取比特图

位图

~bitmap()

析构函数,释放位图空间

位图

init(int n)

初始化位图空间

位图

set(int k)

置位第k个标志位

位图

clear(int k)

复位第k个标志位

位图

test(int k)

取出指定字节中的指定位

位图

dump(char* file)

将位图整体导出至指定的文件

位图

bits2string(int n)

将前n位转换为字符串

位图

expand(int k)

扩容

位图

print(int n)

逐位打印以检验位图内容

位图

(1) bitmap.h

#pragma once

#include

#include

#include

class bitmap { //位图bitmap类

private:

char* M; int N; //比特图所存放的空间M[],容量为N*sizeof(char)*8比特

protected:

void init(int n) //初始化位图空间

{

M = new char[N = (n + 7) / 8]; //申请内存

memset(M,N); //初始化内存块

}

public:

bitmap(int n = 8) { init(n); } //按指定或默认规模创建比特图(为测试暂时选用较小的默认值)

bitmap(char* file,int n = 8) //按指定或默认规模,从指定文件中读取比特图

{

init(n); FILE* fp = fopen(file,”r”); fread(M,sizeof(char),N,fp); fclose(fp);

}

~bitmap() { delete[] M; M = NULL; } //析构时释放比特图空间

void set(int k) //置位第k个标志位

{

expand(k); //拓容

M[k >> 3] |= (0x80 >> (k & 0x07)); //M[第k个标志位所在的字节(k/8 取整)] |= (第k个标志位在所在字节中的位数(取余))

}

void clear(int k) {

expand(k); //拓容

M[k >> 3] &= ~(0x80 >> (k & 0x07)); //M[第k个标志位所在的字节(k/8 取整)] &= ~(第k个标志位在所在字节中的位数(取余))

}

bool test(int k) {//取出指定字节中的指定位

expand(k); //拓容

return M[k >> 3] & (0x80 >> (k & 0x07)); //M[第k个标志位所在的字节(k/8 取整)] &(第k个标志位在所在字节中的位的值)

}

void dump(char* file) //将位图整体导出至指定的文件,以便对此后的新位图批量初始化

{

FILE* fp = fopen(file,”w”); fwrite(M,fp); fclose(fp);

}

char* bits2string(int n)

{ //将前n位转换为字符串——

expand(n – 1); //此时可能被访问的最高位为bitmap[n – 1]

char* s = new char[n + 1]; s[n] = ”; //字符串所占空间,由上层调用者负责释放

for (int i = 0; i < n; i++) s[i] = test(i) ? '1' : '0';

return s; //返回字符串位置

}

void expand(int k)

{ //若被访问的bitmap[k]已出界,则需扩容

if (k < 8 * N) return; //仍在界内,无需扩容

int oldN = N; char* oldM = M;

init(2 * k); //与向量类似,加倍策略

memcpy_s(M,oldM,oldN); delete[] oldM; //原数据转移至新空间

}

void print(int n) //逐位打印以检验位图内容,非必需接口

{

expand(n);

for (int i = 0; i < n; i++)

printf(test(i) ? “1” : “0”);

}

};