在處理海量數據時，我們常常需要檢查某個元素是否已經存在于集合中。傳統的方法如哈希表或集合容器雖然有效，但在數據量極大的情況下會占用大量內存。這時，位圖算法 (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。

位圖算法的優勢與應用場景

位圖算法的主要優勢包括：

• 空間效率極高：每個值只占用一個位，相比傳統方法節省大量內存
• 操作速度快：位運算在現代計算機上非常高效
• 實現簡單：核心邏輯只需要基本的位運算

位圖算法適用于以下場景：

• 數據查重：檢查元素是否已經存在
• 數據排序：可以在位圖上進行高效的排序操作
• 數據統計：統計某個范圍內數據的分布情況