一：位圖的介紹

①：需要位圖的場景

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中？

要判斷一個數是否在某一堆數中，我們可能會想到如下方法：

A：將這一堆數進行排序，然后通過二分查找的方法判斷該數是否在這一堆數中。
B：將這一堆數插入到unordered_set容器中，然后調用find函數判斷該數是否在這一堆數中。

單從方法上來看，這兩種方法都是可以，而且效率也不錯，第一種方法的時間復雜度是O (NlogN ) O(NlogN)O(NlogN)，第二種方法的時間復雜度是O (N)

重點是，40億個數，占用16G的空間，空間消耗是很大的，不可能用代碼直接開辟出16g的空間！

所以，這時候，就需要位圖了

②：位圖的意義

?在上述問題中，我們只需確定某個無符號整數是否存在，即只有兩種可能的狀態（存在或不存在）。因此，可以用一個二進制位來表示無符號整數的狀態：1表示存在，0表示不存在。如圖：

無符號整數總共有232個，因此記錄這些數字就需要232個比特位，也就是512M的內存空間，內存消耗大大減少。?

?③：位圖的概念及使用場景

所謂位圖，就是用每一位來存放某種狀態，適用于海量數據，數據無重復的場景。通常是用來判斷某個數據存不存在的。

二：庫中的位圖的使用方法

①：bitset的定義方式

// 構造一個16位的位圖，所有位都初始化為0。
bitset<16> bs1; //0000000000000000//構造一個16位的位圖，根據所給值初始化位圖的前n位。
bitset<16> bs2(0xfa5); //0000111110100101//構造一個16位的位圖，根據字符串中的0/1序列初始化位圖的前n位。
bitset<16> bs3(string("10111001")); //0000000010111001

解釋：?bs2(0xfa5)

用十六進制數 0xfa5 初始化 bs2;0xfa5 的二進制形式是 111110100101（共 12 位）。

由于 bitset 是 16 位的，而 0xfa5 只有 12 位，因此 高位補 0，最終存儲為：
0000111110100101（16 位）。

②：bieset的成員函數

#include <iostream>
#include <bitset>
using namespace std;int main()
{bitset<8> bs;bs.set(2); //設置第2位bs.set(4); //設置第4位cout << bs << endl; //00010100bs.flip(); //反轉所有位cout << bs << endl; //11101011cout << bs.count() << endl; //6cout << bs.test(3) << endl; //1bs.reset(0); //清空第0位cout << bs << endl; //11101010bs.flip(7); //反轉第7位cout << bs << endl; //01101010cout << bs.size() << endl; //8cout << bs.any() << endl; //1bs.reset(); //清空所有位cout << bs.none() << endl; //1bs.set(); //設置所有位cout << bs.all() << endl; //1return 0;
}

運行結果：

?bitset還有各種運算符的使用.......不再介紹了

三：位圖的模擬實現

前提須知：& 和 | 的規則：

雖然位圖有這么多的函數，但是我們實現，只實現set、reset、tes，已經能讓我們了解bitset了！

①：構造函數

template<size_t N>
class bitset
{//構造函數bitset(){_bits.resize(N/32 + 1, 0); // 初始化所有位為 0}private:vector<int> _bits;};

解釋：N/32+1的意義

我們一般從題目中得到了整形的個數后，用bitset去開辟相應個數的位出來，所以先N/32；

假設現在有50個數，那我們應該開50個位出來，但是50/32只能得到1，所以直接50/32+1等于2，開辟兩個整形出來，即64個位；避免小于32的數字在構造函數里面開辟了0個空間；

②：set函數->將第?x?位設為?1

void set(size_t x)
{assert(x <= N); // 檢查 x 是否越界size_t i = x / 32; // 計算 x 在哪個 int 中size_t j = x % 32; // 計算 x 在該 int 中的比特位位置_bits[i] |= (1 << j); // 將第 j 位設為 1
}

解釋：_bits[i] |= (1 << j)?

旨在：通過位運算將第?j?位設為?1，且不影響其他位。

假設通過前兩步得知我們的x對應的位是vector中第一個整形中的第五個二進制位，所以_bits[1] |= (1 << 5) 的效果如圖：

符合預期，把第5位 置為了1

這例子很簡單，如果原本的vector的其他位也有位1的，這時候進行|=操作后，照樣是不影響其他位的，因為|代表一個為1則為1，兩個為0才是0，所以不影響！

③：reset函數->將第?x?位設為?0

void reset(size_t x)
{assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j); // 將第 j 位設為 0
}

解釋：_bits[i] &=? ~(1 << j)?

通過位運算將第?j?位設為?1，且不影響其他位。

假設通過前兩步得知我們的x對應的位是vector中第一個整形中的第五個二進制位，所以_bits[1] &= ~(1 << 5) 的效果如圖：

符合預期，把第5位 置為了0

這例子很簡單，如果原本的vector的其他位也有位1的，這時候進行&=操作后，照樣是不影響其他位的，因為&代表一個為0則為0，兩個為1才是1，所以不影響！

④：test函數->檢查第?x?位是否為?1

bool test(size_t x)
{assert(x <= N);size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j); // 返回第 j 位的值
}

解釋：_bits[i] & (1 << j);

注意：這一步為何沒有&= 而是 & ，因為該函數只是想看某一位為什么，不能改變該位!

?返回值：若?_bits[i]?的第?j?位為?1，返回?true；否則返回?false。

Q：為什么能判斷某一位是否為 1？

A：& 運算后，只有第 j 位可能非0（因為其他位都是 0）。

如果結果 ≠ 0 → 說明 _bits[i] 的第 j 位是 1（返回 true）。

如果結果 = 0 → 說明 _bits[i] 的第 j 位是 0（返回 false）。

四：位圖總代碼及測試

①：總代碼

#pragma once
#include<assert.h>namespace bit
{template<size_t N>class bitset{public:bitset(){_bits.resize(N/32+1, 0);//cout << N << endl;}// 把x映射的位標記成1void set(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}// 把x映射的位標記成1void reset(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};
}

②：測試代碼

    void test_bitset(){bitset<100> bs1;bs1.set(50);bs1.set(30);bs1.set(90);for (size_t i = 0; i < 100; i++){if (bs1.test(i)){cout << i << "->" << "在" << endl;}else{cout << i << "->" << "不在" << endl;}}bs1.reset(90);bs1.set(91);cout << endl << endl;for (size_t i = 0; i < 100; i++){if (bs1.test(i)){cout << i << "->" << "在" << endl;}else{cout << i << "->" << "不在" << endl;}}

預期效果：100個位中? 第一次打印：50 30 90 位值為1;第二次打印：50 30 91 為1；

運行效果：

符合預期！?

五：位圖相關題目

了解了biset的相關實現后，用庫中的bitset做幾道題目吧~

①：雙位圖找只出現一次的數字

• 場景：從數組中找出所有只出現一次的數字（類似“單身狗”問題）。

• 數組：int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };

• 解決：用?two_bit_set（雙位圖）記錄每個數字的狀態：

  • 10：出現多次。

  • 01：出現一次。

  • 00：未出現。

  • 遍歷數組后，輸出狀態為?01?的數字。

  • ?two_bit_set（雙位圖）的成員變量就是兩個位圖即可

代碼：

#include<iostream>
#include <bitset>
using namespace std;// 雙位圖：獨立類，組合兩個bitset
template<size_t N>
class two_bit_set
{
public:void set(size_t x){if (!_bs1.test(x) && !_bs2.test(x)){_bs2.set(x);  // 00 → 01}else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);  // 01 → 10_bs2.reset(x);}// 10 → 10（無需處理）}bool test(size_t x){if (_bs1.test(x) == false&& _bs2.test(x) == true){return true;}return false;}private:bitset<N> _bs1;  // 高位bitset<N> _bs2;  // 低位};
void test_bitset2()
{int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };two_bit_set<100> bs;for (auto e : a){bs.set(e);}for (size_t i = 0; i < 100; i++){//cout << i << "->" << bs.test(i) << endl;if (bs.test(i)){cout << i << endl;}}
}int main()
{test_bitset2();return 0;
}

②：求兩個數組的交集

• 場景：找出兩個數組中共同存在的數字。

• 兩個數組：int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 }; int a2[] = { 5,3,5,99,6,99,33,66};

• 解決：

  • 用兩個?bitset?分別標記兩個數組的數字。

  • 遍歷所有數字，輸出在兩個位圖中均為?1?的數字。

代碼：

void test_bitset3()
{int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] = { 5,3,5,99,6,99,33,66 };bitset<100> bs1;bitset<100> bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}for (size_t i = 0; i < 100; i++){if (bs1.test(i) && bs2.test(i)){cout << i << endl;}}
}
int main()
{test_bitset3();return 0;
}

運行結果：

此時回到最開始的問題：

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中？

思路：

1：用庫中的位圖開辟40億個位出來

2：讀取題目給的數據，把40億個整形對應的位置為1

3：然后在看待查詢的數對應的位是否為1即可

代碼無法寫出來，因為沒有這個龐大的數據，但是可以了解一下40億位如何開辟：

        bitset<-1> bs2;bitset<UINT_MAX> bs3;bitset<0xffffffff> bs4;

解釋：

1.?bitset<-1> bs2

• 模板參數?size_t N?接受?-1?時會發生隱式轉換

• -1?轉換為?size_t?類型會變成最大值（即?232-1）

2：bitset<UINT_MAX> bs3

標準定義：

• UINT_MAX?是?<climits>?中定義的無符號整數最大值

• 標準值：4,294,967,295（即?232-1）

3：bitset<0xffffffff> bs4

十六進制解析：

• 0xffffffff = 4,294,967,295（即?232-1）

• 完全等價于?bitset<UINT_MAX>

4：bitset<4294967296> bs1;

記得住數字 也可以這樣

③：一些位圖解題的思想

Q：1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數？

A：如果內存不夠，分批次讀是不可靠的，因為有可能在不同的批次中都出現了一次，加起來就超過了題目要求；假設要題目數據總大小1g(1024)，但我們只有512MB；此時我們先讀整數范圍前半部分的值 ?再讀范圍為后半部分的值，先讀0~2^31 ?再讀2^31~2^31-1的范圍即可。

所以空間再小一點都可以，只是要將范圍分細一點罷了
?