理解位图算法：使用 C++ 实现高效数据查重

在处理海量数据时，我们常常需要检查某个元素是否已经存在于集合中。传统的方法如哈希表或集合容器虽然有效，但在数据量极大的情况下会占用大量内存。这时，位图算法 (Bitmap) 就成为了一种非常高效的解决方案。本文将通过分析一段使用位图算法的 C++ 代码，深入探讨这种算法的原理和实现。

位图算法基本原理

位图算法的核心思想是使用一个二进制位 (bit) 来表示某个元素是否存在。每个位对应一个特定的值，如果该值存在，则对应的位被置为 1，否则为 0。这种方法的优势在于它能极大地节省存储空间。例如，使用一个 64 位的long long类型变量，我们可以表示 64 个不同的值，而不是像传统数组那样每个元素占用一个完整的存储单元。

代码实现分析

让我们来分析这段使用位图算法的 C++ 代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<memory>
using namespace std;
typedef long long LL;
int main()
{int num;//元素个数；cin >> num;LL MAX = 0;vector<LL>q;for (int i = 0; i < num; i++){LL sum;cin >> sum;MAX = max(MAX, abs(sum));q.push_back(sum);}const LL len = MAX / 64 + 1;//位图算法，长度由最大值的绝对值/容器数据类型字节大小，long long是64字节的；//LL arr[len]由于len是变量，所以这里没办法在栈上定义了unique_ptr<LL[]>arr(new LL[len]);unique_ptr<LL[]>brr(new LL[len]);LL mod = 64;for (auto it : q){LL sum = 1;if (it > 0){int idx = it / mod;LL num = it % mod;if (arr[idx] >> num)continue;else arr[idx] |= (sum << num);}else{int idx = abs(it) / mod;LL num = abs(it) % mod;if (brr[idx] >> num)continue;else brr[idx] |= (sum << num);}}
}

代码功能解析

这段代码的主要功能是读取一组整数，然后使用位图算法来标记每个数是否存在。代码处理了正数和负数两种情况，下面是详细的步骤解析：

1. 输入处理与最大值计算：

   • 首先读取元素的数量num
   • 依次读取每个元素，并计算它们的绝对值的最大值MAX
   • 将所有元素存储在向量q中

2. 位图数组初始化：

   • 计算位图数组的长度len，公式为MAX / 64 + 1
   • 使用unique_ptr动态分配两个long long类型的数组arr和brr
   • arr用于存储正数的位图
   • brr用于存储负数的位图

3. 位图操作：

   • 遍历每个元素，根据其正负分别处理
   • 对于正数，计算其在位图数组中的索引idx和位偏移num
   • 使用位运算检查该位是否已被设置，如果未设置则设置该位
   • 负数的处理类似，但使用brr数组

位运算详解

在位图算法中，位运算是核心操作。让我们详细解释代码中的位运算部分：

计算索引和位偏移：

int idx = it / mod;  // 计算元素所在的数组索引
LL num = it % mod;   // 计算元素在该索引位置的位偏移

检查位是否已设置：

if (arr[idx] >> num) continue;

这行代码将arr[idx]右移num位，如果结果不为 0，则表示该位已被设置。

设置位：

arr[idx] |= (sum << num);

这行代码将 1 左移num位，然后使用按位或操作将对应位置为 1。

位图算法的优势与应用场景

位图算法的主要优势包括：

• 空间效率极高：每个值只占用一个位，相比传统方法节省大量内存
• 操作速度快：位运算在现代计算机上非常高效
• 实现简单：核心逻辑只需要基本的位运算

位图算法适用于以下场景：

• 数据查重：检查元素是否已经存在
• 数据排序：可以在位图上进行高效的排序操作
• 数据统计：统计某个范围内数据的分布情况