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

C++ 因项目需求，需要将0~2的32次方这个区间的数字保存到内存当中(内存大小为4G),并且可以实现对任意一个数字的增删。(先叙述设计思路，再写岀代码)

news 2025/6/25 18:48:43

问题： C++ 因项目需求，需要将0~2的32次方这个区间的数字保存到内存当中(内存大小为4G),并且可以实现对任意一个数字的增删。(先叙述设计思路，再写岀代码)

解答

设计思路
代码实现
说明

为了在有限的内存（4GB）中存储和操作 0 到 2^32-1 之间的所有数字，我们需要考虑数据结构和存储策略。由于32位整数的范围很大（4,294,967,296 个可能的数字），我们需要一个高效的方式来存储和操作这些数字。在这种情况下，位图（bitmap）是一个合适的选择。

设计思路

位图（Bitmap）：
- 使用位图来表示数字的存在与否，每一个位（bit）对应一个数字。
- 位图的大小需要 2^32 bits（约 512MB），因为每个数字占用1 bit。
内存分配：
- 4GB内存足够容纳整个位图。
- 位图可以使用std::vector<uint8_t>来表示，每个uint8_t包含8个bit。
增删操作：
- 增加数字时，将对应位置的bit设置为1。
- 删除数字时，将对应位置的bit设置为0。
辅助函数：
- 设置位函数：设置特定位置的bit为1。
- 清除位函数：设置特定位置的bit为0。
- 查询位函数：检查特定位置的bit是0还是1。

代码实现

#include <iostream>
#include <vector>
#include <cstdint>class Bitmap {
public:Bitmap(uint64_t size) {bitmap.resize((size + 7) / 8); // 每8个bit为1个byte}// 添加数字void add(uint32_t num) {bitmap[num / 8] |= (1 << (num % 8));}// 删除数字void remove(uint32_t num) {bitmap[num / 8] &= ~(1 << (num % 8));}// 检查数字是否存在bool contains(uint32_t num) const {return bitmap[num / 8] & (1 << (num % 8));}private:std::vector<uint8_t> bitmap;
};int main() 
{Bitmap bitmap(1ULL << 32); // 创建一个包含 2^32 位的位图// 测试添加和删除数字uint32_t num = 123456789;bitmap.add(num);std::cout << "Contains " << num << "? " << (bitmap.contains(num) ? "Yes" : "No") << std::endl;bitmap.remove(num);std::cout << "Contains " << num << "? " << (bitmap.contains(num) ? "Yes" : "No") << std::endl;return 0;
}

说明

Bitmap类：
- bitmap使用std::vector<uint8_t>存储位图数据。
- add方法将对应的bit设置为1。
- remove方法将对应的bit设置为0。
- contains方法检查对应的bit是否为1。
main函数：
- 创建一个Bitmap对象，大小为2^32位。
- 测试添加和删除数字操作。