房产怎么创建网站,做网站视频用哪个视频编辑软件,成都网站建设 推广行,学生管理系统 静态网站源码文章目录 一、引言二、位图#xff08;Bitset#xff09;基础知识1、位图的概念2、位图的表示3、位图操作 三、位图的应用场景1、数据查找与存储2、数据去重与排序 四、位图的实现 一、引言
位图#xff0c;以其高效、简洁的特性在数据处理、存储和检索等多个领域发挥着举足… 文章目录 一、引言二、位图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::bitset8 b; // 创建一个8位的bitset所有位初始化为0
b[3] 1; // 设置第4位为1bitset从右向左计数从0开始清除位Clearing a Bit
要将std::bitset中的特定位清除设置为0同样可以使用下标操作符[]配合赋值操作。
std::bitset8 b(0b11111111); // 创建一个8位的bitset所有位初始化为1
b[3] 0; // 清除第4位设置为0检测位Testing a Bit
要检测std::bitset中的特定位是否为1可以使用下标操作符[]这将返回一个可以转换为bool的类型。
std::bitset8 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::bitset8 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::bitset8 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则表示其对应的数据值存在将其添加到排序数组中。继续这个过程直到检查完位图的所有位。 四、位图的实现
templatesize_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:vectorint _bits;
};
