使用C++實現(xiàn)位圖處理
位圖的引入
無序的40億個不重復(fù)的無符號整數(shù),給一個無符號整數(shù),如何判斷一個數(shù)是否在這40億個數(shù)中
方法1:遍歷, 時間復(fù)雜度O(N)
方法2:排序—O(N*logN) + 二分查找----O(logN)
方法3:可以將所有數(shù)放到unordered_set中,然后調(diào)用find函數(shù)查找
上述的方法存在的問題:
- 這里有40億個數(shù), 若是我們要將這些數(shù)全部加載到內(nèi)存當(dāng)中,那么將會占用16G的空間,空間消耗是很大的
- 因此從空間消耗來看,上述的方法都是不可行的
方法4:利用位圖解決
無符號整數(shù)總共有2^32個,因此記錄這些數(shù)字就需要2^32個比特位,僅僅需要512M的內(nèi)存空間,內(nèi)存消耗大大減少
問:40億個整數(shù)需要占用多少空間
1G =1024*1024*1024 Byte = 10億字節(jié),剛才存放一個整形4個字節(jié),32個比特位,需要16G的空間,現(xiàn)在用一個比特位存,只需要16/32 = 0.5G即可
注意我們需要開辟42億9千多萬個比特位,而不是40億個比特位,因為要映射,要按照整數(shù)的最大范圍去開,而不是按個數(shù)去開 開辟內(nèi)存的最小單位->字節(jié)->用char/int都可以
如何正確開辟42億9前多萬個比特位呢?
共有兩種方式: bitset: template<size_t N> class bitset;
bitset<0xffffffff> bs;//#define UINT_MAX 0xffffffff bitset<-1> bs; //-1的補碼是全1 0xffffffff,而非類型模板參數(shù)的N的參數(shù)是size_t類型
什么是位圖
所謂位圖,就是用每一位來存放某種狀態(tài),適用于海量數(shù)據(jù),數(shù)據(jù)無重復(fù)的場景,通常是用來判斷某個數(shù)據(jù)存不存在的
數(shù)據(jù)是否在給定的整形數(shù)據(jù)中,結(jié)果是在或者不在,剛好是兩種狀態(tài),那么可以使用一個二進(jìn)制比特位來代表數(shù)據(jù)是否存在的信息,如果二進(jìn)制比特位為1,代表存在,為0代表不存在
例子:

位圖的應(yīng)用
- 快速查找某個數(shù)據(jù)是否在一個集合中
- 排序
- 求兩個集合的交集、并集等
- 操作系統(tǒng)中磁盤塊標(biāo)記
- 內(nèi)核中信號標(biāo)志位(信號屏蔽字和未決信號集)
bitset的使用
定義方式
bitset ---> template <size_t N> class bitset; 位圖的大小在編譯時是固定的(由其模板參數(shù)確定)
- 構(gòu)造一個N位的位圖,所有位都初始化為0
- 構(gòu)造一個N位的位圖,根據(jù)所給值初始化位圖的前n位
- 構(gòu)造一個N位的位圖,根據(jù)字符串中的0/1序列初始化位圖的前n位
#include<bitset>
int main()
{
//方式1:構(gòu)造一個N位的位圖,所有位都初始化為0
bitset<16> bs1;//0000 0000 0000 0000
//方式2:構(gòu)造一個N位的位圖,根據(jù)所給值初始化位圖的前n位
bitset<16> bs2(0xabc);//0011 1101 0101 0000
//方式3:構(gòu)造一個N位的位圖,根據(jù)字符串中的0/1序列初始化位圖的前n位
bitset<16> bs3(string("10110001"));//1000 1101 0000 0000
return 0;
}

成員函數(shù)
| 成員函數(shù) | 功能 |
|---|---|
| set | 設(shè)置指定位或所有位為1 |
| reset | 清空指定位或所有位為0 |
| flip | 反轉(zhuǎn)指定位或所有位 |
| test | 獲取指定位的狀態(tài) 0或者1 |
| count | 獲取被設(shè)置位的個數(shù) |
| size | 獲取可以容納的位的個數(shù) |
| any | 判斷是否有位被設(shè)置–>如果有任何一個位被設(shè)置則返回true |
| none | 判斷是否所有位都沒有被設(shè)置->如果沒有位被設(shè)置則返回true |
| all | 判斷是否所有位都設(shè)置->如果所有位都被設(shè)置則返回true |
使用實例:
#include<iostream>
#include<bitset>
int main()
{
//從右到左算起, 最右邊為第0位
bitset<8> bs;//構(gòu)造一個8位的位圖,所有位都初始化為0
bs.set(1);//設(shè)置第1位為1
bs.set(5);//設(shè)置第5位為1
cout << bs << endl; //00100010
bs.flip();//反轉(zhuǎn)bs的所有位
cout << bs << endl;//11011101
cout << "共有"<<bs.count()<<"位被設(shè)置成1" << endl;//共有6位被設(shè)置成1
cout << bs.test(3) << endl;//輸出第3位的狀態(tài) - 1
bs.reset(1);//將第1位設(shè)置為0
cout << bs << endl;//11011101
bs.flip(7);//將第7位反轉(zhuǎn)
cout << bs << endl;//01011101
cout << bs.size() << endl;//輸出位圖可以容納的位的個數(shù) ---8
cout << bs.any() << endl;//判斷是否有位被設(shè)置 ---1
bs.reset();//清空所有位
cout << bs << endl;//00000000
bs.set();//將所有位設(shè)置為1
cout << bs << endl;//11111111
cout << bs.all() << endl;//判斷是否所有位都設(shè)置 ----1
return 0;
}
注意如何區(qū)分成員函數(shù)set,reset,flip是對所有位操作還是對某一個位操作呢?
如果成員函數(shù)帶了參數(shù),就是對該指定的位操作如果沒有指定,就是對所有位操作
bitset的運算符重載
>> 及 << 運算符
我們可以直接使用>> 和 <<運算符對biset容器對應(yīng)的所有位進(jìn)行輸入輸出操作
如果輸入的位數(shù)比位圖所能容納的位數(shù)N多,只會從前向后截取N位
#include<bitset>
int main()
{
bitset<8> bs;
cin >> bs;//輸入:10101
cout << bs << endl;//00010101
return 0;
}
賦值-關(guān)系-復(fù)合賦值-單目運算符
bitset容器對一些復(fù)合賦值運算符和單目運算符也進(jìn)行了重載
- 賦值運算符:
= - 關(guān)系運算符:
==!= - 復(fù)合賦值運算符:
&=|=^=<<=>>= - 單目運算符:
~
#include<bitset>
int main()
{
bitset<8> bs1(string("11111111"));
bitset<8> bs2(string("01010101"));
cout << bs1 << endl;//11111111
bs1 >>= 1;
cout << bs1 << endl;//01111111
bs2 &= bs1;
cout << bs2 << endl;//01010101
return 0;
}
其次我們可以使用& | ^ 對位圖進(jìn)行操作
#include<bitset>
int main()
{
bitset<8> bs1(string("10101111"));
bitset<8> bs2(string("01101101"));
cout << (bs1 | bs2) << endl;//11101111
cout << (bs1 & bs2) << endl;//00101101
cout << (bs1 ^ bs2) << endl;//11000010
return 0;
}
[]重載
bitset容器中對[ ]運算符進(jìn)行了重載,我們可以直接使用[ ]對指定位進(jìn)行訪問或修改
int main()
{
bitset<8> bs(string("11001010"));
cout << bs[0] << endl; //0
bs[0] = 1;
cout << bs << endl; //11001011
return 0;
}
到此這篇關(guān)于使用C++實現(xiàn)位圖處理的文章就介紹到這了,更多相關(guān)C++位圖處理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Qt使用QChart實現(xiàn)靜態(tài)顯示溫度變化曲線
QChart模塊是Qt?Charts庫的基礎(chǔ),提供了用于創(chuàng)建和顯示各種類型圖表的類和接口,本文主要介紹了如何使用QChart實現(xiàn)動態(tài)顯示3個設(shè)備的溫度變化曲線,感興趣的可以了解一下2023-06-06
C++連接mysql數(shù)據(jù)庫的兩種方法小結(jié)
這篇文章主要介紹了C++連接mysql數(shù)據(jù)庫的兩種方法小結(jié),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
Opencv基于CamShift算法實現(xiàn)目標(biāo)跟蹤
這篇文章主要為大家詳細(xì)介紹了Opencv基于CamShift算法實現(xiàn)目標(biāo)跟蹤,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-01-01

