文章目录
- 一、引言
- 二、位图(Bitset)基础知识
- 1、位图的概念
- 2、位图的表示
- 3、位图操作
- 三、位图的应用场景
- 1、数据查找与存储
- 2、数据去重与排序
- 四、位图的实现
一、引言
位图,以其高效、简洁的特性在数据处理、存储和检索等多个领域发挥着举足轻重的作用。通过二进制位的操作,位图能够实现对大量数据的快速访问、修改和查询,从而在众多实际应用场景中展现出其独特的优势。
随着大数据时代的来临,数据量呈现爆炸式增长,如何高效地处理这些数据成为了一个亟待解决的问题。位图技术以其对空间的高效利用和快速的位操作能力,成为了解决这一问题的有力工具。无论是在数据库系统、缓存机制、网络安全,还是在图形处理、用户权限管理等领域,位图都展现出了其不可或缺的价值。
二、位图(Bitset)基础知识
1、位图的概念
- 位图及其基本组成单元(位)
位图(Bitmap)是一种基于二进制位的数据结构,用于高效地存储、检索和管理数据。其基本组成单元是位(Bit),即二进制数中的一个数字,其值只能是0或1。位图通常用于表示一组数据或某种状态的存在与否,其中每个数据项或状态都对应于位图中的一个或多个位。
在C++中,std::bitset
是标准库提供的一种数据结构,用于表示固定大小的位序列,即一个固定长度的二进制序列。它提供了一组方法来进行位操作,例如设置、清除、翻转和测试位等。
std::bitset
的大小在编译时确定,因此它是一种静态大小的位集合。你可以使用std::bitset
来表示和处理布尔值序列,每个位可以代表一个布尔值(true或false)。而且可以单独访问每个位位置:例如,对于名为foo
的位图,表达式foo[3]
访问其第四个位,就像常规数组访问其元素一样。
- 区分位图与像素图的概念
虽然位图在图形处理中也常被提及,但在此上下文中,我们需要明确区分两种不同类型的“位图”:一种是数据结构中的位图,如上所述,它主要用于数据的高效存储和检索;另一种是图形学中的位图,也被称为像素图,它是由像素(Pixel)组成的图像,每个像素都有其特定的颜色和位置。这两种位图在原理和应用上有本质的区别。数据结构中的位图关注的是数据的二进制表示和存储效率,而图形学中的位图则关注的是图像的视觉呈现和细节表现。
2、位图的表示
- 使用二进制表示位图
位图,从数据结构的角度来看,是一种利用二进制位来标记数据存在性的高效方式。在二进制位图中,每一个二进制位(0或1)代表一个数据元素的状态:存在或不存在。通常,我们使用一个整数数组来实现位图,数组中的每个元素(如int或long类型)都由多个二进制位组成。
例如,如果我们使用一个32位的整数(int)来表示位图,那么每个整数可以表示32个不同的数据元素。当我们要标记第n个数据元素是否存在时,我们只需要找到对应的整数(通过n除以32得到整数索引),然后在该整数中找到对应的二进制位(通过n对32取余得到位索引),并将其设置为0或1。
- 位图中位的编址和访问方式
在位图中,位的编址是基于其所在的整数和整数内的位位置来确定的。具体来说,如果我们有一个整数数组bitmap[]
,那么第n个数据元素对应的位在bitmap[n/32]
的第(n%32)
位上。
访问位图中的位通常涉及两个步骤:首先找到对应的整数,然后找到该整数中的对应位。这可以通过位运算来实现。例如,要设置第n位为1,我们可以使用以下代码:
int index = n / 32; // 计算整数索引
int position = n % 32; // 计算位索引
bitmap[index] |= (1 << position); // 设置对应位为1
同样地,要读取第n位的值,我们可以使用以下代码:
int index = n / 32; // 计算整数索引
int position = n % 32; // 计算位索引
int bitValue = (bitmap[index] >> position) & 1; // 读取对应位的值
这里的|=
和&=
是位运算中的赋值操作符,分别表示按位或后赋值和按位与后赋值。<<
和>>
是位移操作符,分别表示左移和右移。通过这些位运算操作,我们可以高效地访问和修改位图中的任意一位。
3、位图操作
在使用std::bitset
时,常见的位操作包括设置位(setting a bit)、清除位(clearing a bit)、检测位(testing a bit)、翻转位(flipping a bit)等。
- 设置位(Setting a Bit)
要将std::bitset
中的特定位设置为1,可以使用下标操作符[]
配合赋值操作。
std::bitset<8> b; // 创建一个8位的bitset,所有位初始化为0
b[3] = 1; // 设置第4位为1(bitset从右向左计数,从0开始)
- 清除位(Clearing a Bit)
要将std::bitset
中的特定位清除(设置为0),同样可以使用下标操作符[]
配合赋值操作。
std::bitset<8> b(0b11111111); // 创建一个8位的bitset,所有位初始化为1
b[3] = 0; // 清除第4位(设置为0)
- 检测位(Testing a Bit)
要检测std::bitset
中的特定位是否为1,可以使用下标操作符[]
,这将返回一个可以转换为bool
的类型。
std::bitset<8> b(0b10101010); // 创建一个8位的bitset
if (b[3]) // 检测第4位是否为1std::cout << "Bit 3 is set." << std::endl;
elsestd::cout << "Bit 3 is not set." << std::endl;
cout << b << endl;
// Bit 3 is set.
//10101010
- 翻转位(Flipping a Bit)
要翻转std::bitset
中的特定位(从0变为1,或从1变为0),可以使用成员函数flip()
。
std::bitset<8> b(0b10101010); // 创建一个8位的bitset
b.flip(3); // 翻转第4位
- 其他操作
std::bitset
还提供了其他有用的成员函数,如:
size()
:返回bitset的大小(位数)。count()
:返回bitset中设置为1的位数。any()
:如果bitset中至少有一个位设置为1,则返回true。none()
:如果bitset中所有位都设置为0,则返回true。all()
:如果bitset中所有位都设置为1,则返回true。to_ulong()
或to_ullong()
:将bitset转换为无符号长整型或无符号长长整型(如果bitset的大小允许)。to_string()
:将bitset转换为字符串表示形式。
std::bitset<8> b(0b10101010);
std::cout << "Size: " << b.size() << std::endl; // 输出bitset的大小
std::cout << "Count: " << b.count() << std::endl; // 输出设置为1的位数
std::cout << "Any: " << b.any() << std::endl; // 检查是否有位设置为1
std::cout << "None: " << b.none() << std::endl; // 检查是否所有位都设置为0
std::cout << "All: " << b.all() << std::endl; // 检查是否所有位都设置为1
std::cout << "Value: " << b.to_ulong() << std::endl; // 转换为无符号长整型并输出
std::cout << "String: " << b.to_string() << std::endl; // 转换为字符串并输出
三、位图的应用场景
1、数据查找与存储
- 使用位图实现快速数据查找
位图可以用于快速查找某个元素是否存在。例如,如果有一个包含大量整数的集合,并且整数的范围已知(例如,从1到1亿),那么可以使用一个位图来表示这个集合。每个整数对应位图中的一个位,如果该整数在集合中,则对应的位被设置为1,否则为0。这样,查找某个整数是否存在只需要检查其对应的位即可,时间复杂度为O(1)。
- 位图在数据存储中的优势
空间效率:相比于存储原始数据,位图可以显著节省存储空间。在上面的例子中,如果使用一个整型数组来存储集合中的元素,每个整数需要4个字节(假设是32位系统),那么存储1亿个整数需要大约400MB的空间。而使用位图,只需要大约12MB的空间(1亿个位,每个位1/8字节)。
-
使用整型数组:如果每个整数占用4个字节(在32位系统中,一个
int
通常是32位,即4字节),那么存储1亿个整数将需要大约400MB的空间,计算如下:1亿个整数 * 4字节/整数 = 400,000,000字节 400,000,000字节 / 1024 / 1024 = 381.47MB (约等于400MB)
-
使用位图:在位图中,每个位占用1/8字节(因为1字节 = 8位)。所以,存储1亿个位将需要大约12MB的空间,计算如下:
1亿个位 * 1/8字节/位 = 12,500,000字节 12,500,000字节 / 1024 / 1024 = 11.92MB (约等于12MB)
若给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中?
步骤 1: 确定位图大小
首先,需要确定无符号整数的位数,这决定了位图的大小。假设我们处理的是32位无符号整数,那么整数的范围是从0到232 - 1。因此,你需要一个位图,其中包含232个位,每个位对应一个可能的整数。
步骤 2: 分配内存
接下来,就需要分配足够的内存来存储这个位图。由于每个位可以是0或1,可以使用位操作来紧凑地存储这些位。在实际应用中,通常会使用一个字节数组(byte array)或位数组(bit array)来表示位图。
对于一个包含232个位的位图,你需要大约512MB的内存(因为232位 / 8位/字节 = 229字节 = 512MB)。
步骤 3: 初始化位图
将位图中的所有位初始化为0,表示没有任何整数被标记为存在。
步骤 4: 填充位图
遍历40亿个无符号整数,对于每个整数,计算它在位图中的索引,并将该索引对应的位设置为1。索引的计算通常是通过整数本身直接转换得到的。例如,对于一个32位整数
num
,你可以直接将其用作索引(可能需要一些转换来适应字节数组的索引方式)。步骤 5: 查询整数
当需要查询一个整数是否存在于集合中时,你只需计算该整数在位图中的索引,并检查该索引对应的位是否为1。如果是1,表示该整数存在于集合中;如果是0,表示不存在。
有了上面的思路方法,我们来解决如下问题:
一、给定100亿个整数,我们如何找到只出现一次的整数呢?
由于整数可能有正有负,我们先假设整数的范围是已知的,例如是32位有符号整数。使用一个标准的位图来记录每个整数出现的次数。但需要扩展位图的概念,使得每个整数对应多个位,用以计数。例如,可以使用2个位来表示一个整数出现的次数:00表示0次,01表示1次,10表示2次或更多。
📽 我们可以这样做:
初始化一个大小为
2 * INT_MAX + 1
的位图(考虑负数和0),每个整数对应2位。遍历整数集合,对每个整数更新其对应的计数器。
- 如果对应位是00,则设置为01。
- 如果是01,则设置为10。
- 如果是10,则保持不变(因为我们只关心出现1次的)。
再次遍历位图,找出所有对应位为01的整数。
二、给两个文件,分别有100亿个整数,我们只有1G内存,如何找到?
首先,假设这些整数是32位无符号整数,那么理论上需要4GB的内存来存储一个完整的位图(因为232位 = 4GB)。由于只有1GB的内存可用,因此不能一次性加载所有整数到位图中。
因此我们借助哈希函数,分块处理。
- 准备阶段
- 先设计一个哈希函数。这个函数的任务是,当我们给它一个整数时,它会告诉我们这个整数应该属于哪个“小团队”。想象一下,我们有1000个“小团队”,每个团队负责处理大约1000万个整数。
- 处理第一个文件
- 我们开始遍历第一个文件,对里面的每个整数都用哈希函数“问问路”,看它们应该属于哪个“小团队”。
- 比如,哈希函数告诉我们某个整数应该属于“团队500”,那我们就把这个整数记录到 “a500” 这个文件里。
- 这样,我们就把第一个大文件拆分成了1000个小文件,每个文件大约40M,这样我们的1G内存就能轻松应对了。
- 处理第二个文件
- 对第二个文件也如法炮制。还是使用相同的哈希函数,把整数分配到它们各自的“小团队”中。
- 这次我们把结果记录在b1, b2, …, b1000这一系列文件中。
- 找交集
- 有了这两组“小团队”,我们就可以开始找交集了。
- 由于我们是用同样的哈希函数来分配整数的,所以,如果两个文件中有共同的整数,那么这些整数一定会出现在同样编号的“小团队”里。
- 比如,a500和b500里就应该有相同的整数,我们只需要在这两个文件里找交集就行了。
- 这样,我们就在每个“小团队”内部找交集,由于数据量小了很多,这个任务就变得容易多了。
- 汇总成果
- 最后,我们把所有“小团队”找到的交集汇总起来,就是我们要找的答案了。
2、数据去重与排序
使用位图去除数据集中的重复元素。
基于位图的排序算法通常适用于数据值范围已知且较小的情况。其原理是利用位图来记录每个数据值的出现情况,并根据位图的顺序生成已排序的数组。具体步骤如下:
- 初始化位图:创建一个能够覆盖所有数据值的位图,并初始化为0。
- 遍历并设置位图:遍历原始数据,对于每个数据值,将其对应的位在位图中设置为1。
- 生成排序数组:从位图的最低位开始,依次检查每个位。如果某个位为1,则表示其对应的数据值存在,将其添加到排序数组中。继续这个过程,直到检查完位图的所有位。
四、位图的实现
template<size_t N>
class bitset {
public:bitset( ) {_bits.resize(N / 32 + 1, 0);}// 把 x 映射的位 标记成 1void set(size_t x) {assert(x < N);size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}// 把 x 映射的位 标记成 0void reset(size_t x) {assert(x < N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x) {size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}
private:vector<int> _bits;
};