位图 (bitmap)

介绍

一种可以有效压缩空间的数据结构，用整数的 位(bit) 来表示 数据 p 的状态（0/1），将这个整数作为数组的一个元素，构造一个这样的数组，数组的下标为 整数的个数，整数的二进制值 为 所存储的数据。

简单来说就是以一个整数 A 的二进制位来表示某个数据是否存在，这样的整数 A 构成了一个数组，这个数组就成为了 bitmap。

最基本的情况，使用一个bit表示一个关键字的状态（可表示两种状态 0/1）

思路与实现

整数 A 可以用二进制拆分成一个01数组，我们是不是可以用这个01数组来存储一些东西？

一个byte = 8 bit,使用bit为单位，使用二进制来存储数据。

因此一个位能保存 0/1 两个值，用来表示是否存在数据。

这里给出一个表，便于理解。

存储数据为 [1,2,6,7,10,15]

这里是每个数组元素开辟空间为 1 byte，如果使用 int 数组 每个数组元素开辟空间就为 4 byte，每个数据压缩32倍，

相应的存储范围变为 (0~31，32~63)，同理 使用 long long 数组每个元素开辟空间就为 8 byte ，每个数据压缩64倍......

如果扩展到 __int128_t 就可以使得单位存储范围达到 128 位，每个数据压缩128倍

这样一来，如果有20亿个int数据要处理，占用内存 左右，而使用bitmap后，只需要

查询数据是否存在（校验）

假设给出数据为 ，当前存储结构为 int bitmap[bitmap_size]，则该数据的位置为 bitmap[(int)(p>>5)] 的 (p&31) 位 即 bitmap[(int)(p>>5)] 的第 (p&31) 位 （ bitmap[int(p/32)] 的 (p%32) 位）

查询是否存在只需要去判断 bitmap[(int)(p>>5)] 的第 (p&31) 位 是否为 1 即可，转换一下就是判断

bitmap[(int)(p>>5)] & (1 << (p&31)) 是否为 1 ，因此时间复杂度为

bool check(int p)
{
    // return bitmap[p/32] & (1<<(p%32));
    return bitmap[(int)(p>>5)] & (1 << (p&31));
}

插入数据

插入数据与查询相似， bitmap[(int)(p>>5)] 的第 (p&31) 位 置 1 即可。

bool set(int p)
{
    if((int)p>>5 > bitmap_size)return 0;
    bitmap[(int)(p>>5)] |= 1 >> (p&31);
    return 1;
}

删除数据

删除数据即插入数据的反向操作，将 1 左移 (p&31) 位，然后按位取反，最后与 bitmap 做与操作就可以把该位置 (p&31) 置零了，即删除数据 p。时间复杂度与插入数据相同

bool remove(int p)
{
    if((int)(p>>5) > bitmap_size)return 0;
    bitmap[(int)(p>>5)] &= ~(1 << (p&31));
}

查询数据（按下标查询 a[]操作 ）

根据下标 ( total_index ) 查询数据（取值），相当于数组的 a 操作，时间复杂度为

int getValue(int total_index)
{
    int size = (int)(bitmap_size << 5);
    int index = 0;
    for(int i = 0;i < size; i++)
    {
        if(check(i))
            if(index == total_index)return i;
        index++;
    }
    return 0;
}

应用场景和优缺点

应用场景

• 适用于大量数据的排序、存储、查询、去重。
• 在使用hash的情况下可以对字符串等数据类型进行存储。
• 取两个集合的交并集（例如去求两个场景下某些功能的使用情况）

优点

• 内存占用低，资源消耗小，可以极大降低时间复杂度和空间复杂度。
• 运算效率高，校验数据时间复杂度，按下标查询数据时间复杂度，修改数据时间复杂度

缺点

• 由于是以 第 i 位来表示数据是否存在，因此要求存储的数据必须为非负整数类型。
• 同样的原因，存储的元素也不能重复

STL::bitset

bitset就是bitmap算法在C++里面被封装起来了，也是用位来表示一个数，bitset支持与(unsigned)（long long) int、bool、string之间的相互转化。

用法

引用

#include <bitset>

构造

使用 bitset name 构造一个bitset变量

// 比如去构造一个存储位数128位的bitset，变量名称为bitmap，初始值为 0
bitset<128>bitmap(0);
// bitmap = 00000000...00000 (128个0)

这里的初始值指的是 将初始值的二进制数 放入bitset，举个栗子

bitset<8>bitmap_1(3);
// bitmap_1 = 00000011
bitset<8>bitmap_2(4);
// bitmap_1 = 00000100
// 也可以用01字符串
bitset<8>bitmap_3("1001");
// bitmap_1 = 00001001

修改数据

与自己实现的不同，bitset支持像下面这样赋值。

bitmap[x] = 1;

看起来比较像string，不同的是他还支持位运算 ( &、|、~、^、<<、>> )

内置函数

c.size()      // 返回大小（位数）
c.count()     // 返回1的个数
c.any()       // 返回是否有1
c.none()      // 返回是否没有1
c.set()       // 全都变成1
c.set(p)      // 将第p + 1位变成1
c.set(p, x)   // 将第p + 1位变成x
c.reset()     // 全都变成0
c.reset(p)    // 将第p + 1位变成0
c.flip()      // 全都取反
c.flip(p)     // 将第p + 1位取反
c.to_ulong()  // 返回它转换为unsigned long的结果，如果超出范围则报错
c.to_ullong() // 返回它转换为unsigned long long的结果，如果超出范围则报错
c.to_string() // 返回它转换为string的结果