在處理海量數據時,我們常常需要檢查某個元素是否已經存在于集合中。傳統的方法如哈希表或集合容器雖然有效,但在數據量極大的情況下會占用大量內存。這時,位圖算法 (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);}}
}
代碼功能解析
這段代碼的主要功能是讀取一組整數,然后使用位圖算法來標記每個數是否存在。代碼處理了正數和負數兩種情況,下面是詳細的步驟解析:
-
輸入處理與最大值計算:
- 首先讀取元素的數量
num
- 依次讀取每個元素,并計算它們的絕對值的最大值
MAX
- 將所有元素存儲在向量
q
中
- 首先讀取元素的數量
-
位圖數組初始化:
- 計算位圖數組的長度
len
,公式為MAX / 64 + 1
- 使用
unique_ptr
動態分配兩個long long
類型的數組arr
和brr
arr
用于存儲正數的位圖brr
用于存儲負數的位圖
- 計算位圖數組的長度
-
位圖操作:
- 遍歷每個元素,根據其正負分別處理
- 對于正數,計算其在位圖數組中的索引
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。
位圖算法的優勢與應用場景
位圖算法的主要優勢包括:
- 空間效率極高:每個值只占用一個位,相比傳統方法節省大量內存
- 操作速度快:位運算在現代計算機上非常高效
- 實現簡單:核心邏輯只需要基本的位運算
位圖算法適用于以下場景:
- 數據查重:檢查元素是否已經存在
- 數據排序:可以在位圖上進行高效的排序操作
- 數據統計:統計某個范圍內數據的分布情況