目錄

1.位圖的引入

2.位圖概念

3.位圖的實現

3.1前提準備

3.2set

3.3reset

3.4test

4.位圖的應用

---

1.位圖的引入

給40億個不重復的無符號整數，沒排過序

再給一個無符號整數，如何快速判斷這個無符號整數是否在 這40億個數中

首先，一個無符號整數占4個字節，40億個無符號整數占160億字節

其次，1GB = 1024MB = 1024*1024KB = 1024*1024*1024Byte 約等于 10億+ 字節

那么40億個無符號整數需要約16G的內存，超出普通計算機的容量，更別提

使用哈希(指針等額外開銷)、排序后二分查找(內存壓力未解決)判斷，

解決方法：使用位圖標記

數據是否在給定的整形數據中，結果是在或者不在，剛好是兩種狀態，那么可以使用一 個二進制比特位來代表數據是否存在的信息，如果二進制比特位為1，代表存在，為0 代表不存在

2.位圖概念

位圖就是用比特位表示一個數據的狀態信息，適用于海量數據，數據無重復的場景。通常是用來判斷某個數據存不存在的

位圖就是將數據與數據在位圖中對應的比特位進行了一一對應，是哈希的一種變形

3.位圖的實現

用字節進行位運算，我們可以操縱某一個比特位為0或者為1

因為位運算操作的是數據的二進制位模式，而非內存中的字節順序，所以我們不必關注端序

只是在畫圖的時候需要關注一下端序(大小端)

3.1前提準備

#pragma once
#include<vector>
namespace dfq
{template<size_t N>class bitset{public:bitset(){_a.resize(N / 32 + 1);}private:vector<int> _a;};
}

(1)C++庫里面有 bitset 的實現，創建命名空間避免命名沖突
(1)非類型模板參數N表示要開多大的空間
(1)使用一個整型或者char類型的數組，通過字節位運算操縱比特位
(1)構造函數，向上取整開空間

3.2set

//將x映射的那個位置變為1
void set(size_t x)
{size_t i = x / 32;//i標識x映射到_a的第幾個位置size_t j = x % 32;//j標識x映射到4個字節中的哪一個位置_a[i] |= (1 << j);
}

(1)??i 標識x映射到_a的第幾個位置
(2)?j 標識x映射到4個字節中的哪一個位置

(3) 數組中對應數據的對應二進制位變為1

| 或運算的特點，有1為1，0與其他數進行或運算等于其他數本身
<< 左移運算符的特點，數據的二進制為向高位移動，左邊舍棄，右邊補0

......... 0 ...........   == _a[i]00000000001000000000000   == 1 << j

3.3reset

//將x映射的那個位置變為0
void reset(size_t x)
{size_t i = x / 32;//i標識x映射到_a的第幾個位置size_t j = x % 32;//j標識x映射到4個字節中的哪一個位置_a[i] &= ~(1 << j);
}

(1) 數組中對應數據的對應二進制位變為0

& 與運算的特點，有0為0，1與其他數進行與運算等于其他數本身
<< 左移運算符的特點，數據的二進制為向高位移動，左邊舍棄，右邊補0

~ 按位取反運算特點，數據的二進制位 1 變 0，0變1

......... 1 ...........   == _a[i]00000000001000000000000   == 1 << j11111111110111111111111   == ~(1 << j)

3.4test

bool test(size_t x)
{size_t i = x / 32;//i標識x映射到_a的第幾個位置size_t j = x % 32;//j標識x映射到4個字節中的哪一個位置return _a[i] & (1 << j);
}

_a[i] & (1 << j) 的意思是：

數據存在，數組中對應數據的對應比特位為1，表達式不為0，為真

數據不存在，數組中對應數據的對應比特位為0，表達式為0，為假

4.位圖的應用

1. 給定100億個整數，設計算法找到只出現一次的整數？

(1)使用兩個位圖 bs1、bs2 (根據范圍開空間)

(2)從文件中讀取數據，調用set函數進行標記，標記原理及規則如下：

bs1、bs2對應的比特位一個有 00、01、10、11四種情況，我們取前面三種

• 初始條件下，bs1、bs2比特位均為0
• 數據第一次出現(!_bs1.test(x) && !_bs2.test(x))，bs2.set(x)
• 數據第二次出現(!_bs1.test(x) && _bs2.test(x))，bs1.set(x);bs2.reset(x)
• 三次以上就不進行統計了

(3)bs1、bs2對應的比特位組合為01的數就是只出現一次的整數

template<size_t N>
class twobitset
{
public://x映射的那個值變為1void set(size_t x){//00 -> 01if (!_bs1.test(x) && !_bs2.test(x))_bs2.set(x);//01 -> 10else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}//10 就不變了}//檢測x是否只存在一次bool is_once(size_t x){return !_bs1.test(x) && _bs2.test(x);}private:bitset<N> _bs1;bitset<N> _bs2;
};

2. 給兩個文件，分別有100億個整數，我們只有1G內存，如何找到兩個文件交集？

將兩個序列分別映射到兩個位圖上，對兩個位圖的每個字節進行按位與操作，結果為1 的比特位對應的數據的就是兩個序列的交集

3. 位圖應用變形：1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整 數

與第一題的思路一致，使用兩個位圖統計次數，00、01、10、11

• 初始條件下，bs1、bs2比特位均為0
• 數據第一次出現(!_bs1.test(x) && !_bs2.test(x))，bs2.set(x)
• 數據第二次出現(!_bs1.test(x) && _bs2.test(x))，bs1.set(x);bs2.reset(x)
• 數據第三次出現(_bs1.test(x) && !_bs2.test(x))，bs2.set(x)
• 四次以上就不進行統計了

總結位圖的應用：

1. 快速查找某個數據是否在一個集合中

2. 排序 + 去重

3. 求兩個集合的交集、并集等

4. 操作系統中磁盤塊標記