1.位圖概念

和哈希一樣，都是一個表來記錄某個元素的個數或者存在與否；不同的是哈希使用的計算機定義的完整空間向數組的int類型；而位圖則是時使用的一個或者多個（不會太多）bit位來表示表示一個數字的個數或者存在與否。

2.位圖的實現

第一步定義空間.
位圖由于是使用bit位來記錄的，但是單個bit位無法開出來，所以我們先可以使用int定義出來空間（即定義一個可以下位圖的空間）；

第二步定義類中的接口
構造函數：

輸入函數：

刪除函數：

查找函數：

解釋i和j：
這里刪除函數和輸入函數的i表示的是：數x在數組的第幾個數；
這里刪除函數和輸入函數的j表示的是：數x在數組的第i個數的第幾個bit位；

代碼

	//位圖template<size_t N>class bitset{public:bitset(){//_bits.resize(N/32+1,0);_bits.resize((N >> 5) + 1, 0);}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};

3.應用（解決整形存在或次數問題）

3.1存在問題

在【42，39】中是否存在39，40，41，42；
頭文件和上面的一樣

template<size_t N>class bitset{public:bitset(){//_bits.resize(N/32+1,0);_bits.resize((N >> 5) + 1, 0);}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};

源文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"bitset.h"
int main()
{bit::bitset<100> bs;bs.set(40);bs.set(39);cout << bs.test(38) << endl;cout << bs.test(39) << endl;cout << bs.test(40) << endl;cout << bs.test(41) << endl;cout << bs.test(42) << endl << endl;return 0;
}

3.2次數問題

題目：查找【1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 】中出現一次和兩次的數字
對比存在問題需將插入函數和輸出函數修改即可修改在下：
頭文件：

 template<size_t N>class twobitset{public:void set(size_t x){//00->01//01->10//10->11//11->不變if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) == true && _bs2.test(x) == false){_bs1.set(x);_bs2.set(x);}}void Print(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout << "1->" << i << endl;}else if (_bs1.test(i) == true && _bs2.test(i) == false){cout << "2->" << i << endl;}}cout << endl;}private:bitset<N> _bs1;bitset<N> _bs2;};

源文件：

int main()
{int a[] = { 1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 };bit::twobitset<100> bs;for (auto e : a){bs.set(e);}bs.Print();return 0;
}

5.搜索的方法對比：