当前位置：首页 > news >正文

【C++补充】第一弹---位图技术揭秘：内存优化与快速访问

news 来源：原创 2025/5/9 3:55:59

✨个人主页：熬夜学编程的小林

💗系列专栏：【C语言详解】【数据结构详解】【C++详解】

1 位图

1.1 位图相关面试题

1.2 位图的设计及实现

1.3 C++库中的位图 bitset

1.4 位图的模拟实现

1.5 位图的优缺点

1.6 位图相关考察题目

1 位图

1.1 位图相关面试题

1. 面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。（本题为腾讯/百度等公司出过的⼀个⾯试题）

解题思路1：暴力遍历，时间复杂度O(N)，太慢

解题思路2：排序+⼆分查找。时间复杂度消耗 O(N*logN) + O(logN)

深入分析：解题思路2是否可⾏，我们先算算40亿个数据⼤概需要多少内存。
1G = 1024MB = 1024*1024KB = 1024*1024*1024Byte 约等于10亿多Byte
那么40亿个整数约等于16G，说明40亿个数是无法直接放到内存中的，只能放到硬盘文件中。而⼆分查找只能对内存数组中的有序数据进行查找。
解题思路3：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用⼀个⼆进制比特位来代表数据是否存在的信息，如果⼆进制比特位为1，代表存在，为0代表不存在。那么我们设计⼀个用位表示数据是否存在的数据结构，这个数据结构就叫位图。

比如：

1.2 位图的设计及实现

位图本质是⼀个直接定址法的哈希表，每个整型值映射⼀个bit位，位图提供控制这个bit的相关接⼝。

实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的比特位。比如我们数据存到vector<int>中，相当于每个int值映射对应的32个值，比如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后⾯的以此类推，那么来了⼀个整形值x，i = x / 32；j = x % 32；计算出x映射的值在vector的第i个整形数据的第j位。

解决给40亿个不重复的⽆符号整数，查找⼀个数据的问题，我们要给位图开2^32个位，注意不能开40亿个位，因为映射是按大小映射的，我们要按数据大小范围开空间，范围是是0-2^32-1，所以需要开2^32个位。然后从文件中依次读取每个set到位图中，然后就可以快速判断⼀个值是否在这40亿个数中了。

注意：C++库中的位图不能直接开辟2^32个位的空间，需要通过指针new这么大的空间，代码如下：

#include<iostream>
#include<bitset>
using namespace std;int main()
{// 开2^32个位的位图//std::bitset<-1> bs1;// C++库开不了这么大空间//std::bitset<0xffffffff> bs2;// INT_MAX ->2,147,483,647 ->7FFF FFFF// UINT_MAX -> 0xffffffff//std::bitset<UINT_MAX> bs3;std::bitset<-1>* ptr = new std::bitset<-1>();// C++库能够new这么多空间return 0;
}

开辟成功

开辟失败

快速判断⼀个值是否在这40亿个数中？

代码演示

#include<iostream>
#include<bitset>
using namespace std;int main()
{std::bitset<-1>* ptr =  new std::bitset<-1>();int a[] = { 5,7,9,2,5,9,5,5,7,5,3,9,2,5,1,5,6,6,6,6,7,9 };for (auto e : a){ptr->set(e);}// 判断一个数是否在上面的数组中for (size_t i = 0; i < 10; i++){if (ptr->test(i)){cout << i << "->" << "在" << endl;}else{cout << i << "->" << "不在" << endl;}}return 0;
}

运行结果

1.3 C++库中的位图 bitset

可以看到核心接⼝还是set/reset/和test，当然后面还实现了⼀些其他接⼝，如to_string将位图按位转成01字符串，再包括operator[]等⽀持像数组⼀样控制⼀个位的实现

代码演示

#include<iostream>
#include<bitset>
using namespace std;int main()
{bitset<100> bs1;// 返回位数，非类型参数Ncout << bs1.size() << endl;// 位数为1个总个数cout << bs1.count() << endl;bitset<10> bs2(5);cout << bs2.count() << endl;cout << bs2 << endl;// 将第一位设置为1bs2.set(1);cout << bs2 << endl;// 将第零为设置为0bs2.reset(0);cout << bs2 << endl;// 检查第二位是否为1cout << bs2.test(2) << endl;return 0;
}

运行结果

1.4 位图的模拟实现

基本结构

template<size_t N>
class bitset
{
public:// 构造函数bitset();// x映射的位标记成1void set(size_t x);// x映射的位标记成0void reset(size_t x);// x映射的位是1返回真，0返回假bool test(size_t x);
private:vector<int> _bs;
};

构造函数

bitset()
{// 扩容，不管能否整除都多开一个空间_bs.resize(N / 32 + 1);
}

set()

// x映射的位标记成1
void set(size_t x)
{size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);
}

分析

reset()

// x映射的位标记成0
void reset(size_t x)
{size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));
}

分析

test()

// x映射的位是1返回真，0返回假
bool test(size_t x)
{size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);
}

分析

1.5 位图的优缺点

优点：增删查改快，节省空间
缺点：只适用于整形

1.6 位图相关考察题目

• 给定100亿个整数，设计算法找到只出现⼀次的整数？
虽然是100亿个数，但是还是按范围开空间，所以还是开2^32个位，跟前面的题目是⼀样的。
• 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集
• ⼀个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数？

根据上面的题意，我们需要通过位图实现一个能表示出现0次，1次，2次，多次的位图，因此可以实现一个两个位图成员的类。

基本类

namespace lin
{template<size_t N>class twobitset{public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) // 00->01{_bs2.set(x);}else if (!bit1 && bit2) // 01->10{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2) // 10->11{_bs1.set(x);_bs2.set(x);}}// 返回0 出现0次数// 返回1 出现1次数// 返回2 出现2次数// 返回3 出现2次及以上int get_count(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2){return 0;}else if (!bit1 && bit2){return 1;}else if (bit1 && !bit2){return 2;}else{return 3;}}private:bitset<N> _bs1;bitset<N> _bs2;};
}

1、只出现⼀次的整数？

代码演示

void test_twobitset1()
{lin::twobitset<100> tbs;int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}// 只出现一次的整数for (size_t i = 0; i < 100; ++i){if (tbs.get_count(i) == 1){cout << i << endl;}}
}

运行结果

2、找到两个文件交集？

代码演示

void test_bitset()
{int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] = { 5,3,5,99,6,99,33,66 };bitset<100> bs1;bitset<100> bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}// 两个文件的交集for (size_t i = 0; i < 100; i++){// 第i的位置都是1就是交集if (bs1.test(i) && bs2.test(i)){cout << i << endl;}}
}

运行结果

3、出现次数不超过2次的所有整数(出现1次和2次)？

代码演示

void test_twobitset2()
{lin::twobitset<100> tbs;int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}// 出现次数不超过2次的所有整数for (size_t i = 0; i < 100; ++i){//cout << i << "->" << tbs.get_count(i) << endl;if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2){cout << i << endl;}}
}

运行结果

1 位图

1.1 位图相关面试题

1.2 位图的设计及实现

1.3 C++库中的位图 bitset

1.4 位图的模拟实现

1.5 位图的优缺点

1.6 位图相关考察题目

相关文章：