使用C++實(shí)現(xiàn)位圖處理
位圖的引入
無(wú)序的40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù),給一個(gè)無(wú)符號(hào)整數(shù),如何判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中
方法1:遍歷, 時(shí)間復(fù)雜度O(N)
方法2:排序—O(N*logN) + 二分查找----O(logN)
方法3:可以將所有數(shù)放到unordered_set
中,然后調(diào)用find函數(shù)查找
上述的方法存在的問(wèn)題:
- 這里有40億個(gè)數(shù), 若是我們要將這些數(shù)全部加載到內(nèi)存當(dāng)中,那么將會(huì)占用16G的空間,空間消耗是很大的
- 因此從空間消耗來(lái)看,上述的方法都是不可行的
方法4:利用位圖解決
無(wú)符號(hào)整數(shù)總共有2^32個(gè),因此記錄這些數(shù)字就需要2^32個(gè)比特位,僅僅需要512M的內(nèi)存空間,內(nèi)存消耗大大減少
問(wèn):40億個(gè)整數(shù)需要占用多少空間
1G =1024*1024*1024 Byte = 10億字節(jié),剛才存放一個(gè)整形4個(gè)字節(jié),32個(gè)比特位,需要16G的空間,現(xiàn)在用一個(gè)比特位存,只需要16/32 = 0.5G即可
注意我們需要開(kāi)辟42億9千多萬(wàn)個(gè)比特位,而不是40億個(gè)比特位,因?yàn)橐成?要按照整數(shù)的最大范圍去開(kāi),而不是按個(gè)數(shù)去開(kāi) 開(kāi)辟內(nèi)存的最小單位->字節(jié)->用char/int都可以
如何正確開(kāi)辟42億9前多萬(wàn)個(gè)比特位呢?
共有兩種方式: bitset: template<size_t N> class bitset;
bitset<0xffffffff> bs;//#define UINT_MAX 0xffffffff bitset<-1> bs; //-1的補(bǔ)碼是全1 0xffffffff,而非類(lèi)型模板參數(shù)的N的參數(shù)是size_t類(lèi)型
什么是位圖
所謂位圖,就是用每一位來(lái)存放某種狀態(tài),適用于海量數(shù)據(jù),數(shù)據(jù)無(wú)重復(fù)的場(chǎng)景,通常是用來(lái)判斷某個(gè)數(shù)據(jù)存不存在的
數(shù)據(jù)是否在給定的整形數(shù)據(jù)中,結(jié)果是在或者不在,剛好是兩種狀態(tài),那么可以使用一個(gè)二進(jìn)制比特位來(lái)代表數(shù)據(jù)是否存在的信息,如果二進(jìn)制比特位為1,代表存在,為0代表不存在
例子:
位圖的應(yīng)用
- 快速查找某個(gè)數(shù)據(jù)是否在一個(gè)集合中
- 排序
- 求兩個(gè)集合的交集、并集等
- 操作系統(tǒng)中磁盤(pán)塊標(biāo)記
- 內(nèi)核中信號(hào)標(biāo)志位(信號(hào)屏蔽字和未決信號(hào)集)
bitset的使用
定義方式
bitset ---> template <size_t N> class bitset;
位圖的大小在編譯時(shí)是固定的(由其模板參數(shù)確定)
- 構(gòu)造一個(gè)N位的位圖,所有位都初始化為0
- 構(gòu)造一個(gè)N位的位圖,根據(jù)所給值初始化位圖的前n位
- 構(gòu)造一個(gè)N位的位圖,根據(jù)字符串中的0/1序列初始化位圖的前n位
#include<bitset> int main() { //方式1:構(gòu)造一個(gè)N位的位圖,所有位都初始化為0 bitset<16> bs1;//0000 0000 0000 0000 //方式2:構(gòu)造一個(gè)N位的位圖,根據(jù)所給值初始化位圖的前n位 bitset<16> bs2(0xabc);//0011 1101 0101 0000 //方式3:構(gòu)造一個(gè)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è)置位的個(gè)數(shù) |
size | 獲取可以容納的位的個(gè)數(shù) |
any | 判斷是否有位被設(shè)置–>如果有任何一個(gè)位被設(shè)置則返回true |
none | 判斷是否所有位都沒(méi)有被設(shè)置->如果沒(méi)有位被設(shè)置則返回true |
all | 判斷是否所有位都設(shè)置->如果所有位都被設(shè)置則返回true |
使用實(shí)例:
#include<iostream> #include<bitset> int main() { //從右到左算起, 最右邊為第0位 bitset<8> bs;//構(gòu)造一個(gè)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;//輸出位圖可以容納的位的個(gè)數(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
是對(duì)所有位操作還是對(duì)某一個(gè)位操作呢?
如果成員函數(shù)帶了參數(shù),就是對(duì)該指定的位操作如果沒(méi)有指定,就是對(duì)所有位操作
bitset的運(yùn)算符重載
>> 及 << 運(yùn)算符
我們可以直接使用>>
和 <<
運(yùn)算符對(duì)biset容器對(duì)應(yīng)的所有位進(jìn)行輸入輸出操作
如果輸入的位數(shù)比位圖所能容納的位數(shù)N多,只會(huì)從前向后截取N位
#include<bitset> int main() { bitset<8> bs; cin >> bs;//輸入:10101 cout << bs << endl;//00010101 return 0; }
賦值-關(guān)系-復(fù)合賦值-單目運(yùn)算符
bitset容器對(duì)一些復(fù)合賦值運(yùn)算符和單目運(yùn)算符也進(jìn)行了重載
- 賦值運(yùn)算符:
=
- 關(guān)系運(yùn)算符:
==
!=
- 復(fù)合賦值運(yùn)算符:
&=
|=
^=
<<=
>>=
- 單目運(yùn)算符:
~
#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; }
其次我們可以使用&
|
^
對(duì)位圖進(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容器中對(duì)[ ]運(yùn)算符進(jìn)行了重載,我們可以直接使用[ ]對(duì)指定位進(jìn)行訪問(wè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++實(shí)現(xiàn)位圖處理的文章就介紹到這了,更多相關(guān)C++位圖處理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Qt音視頻開(kāi)發(fā)之利用ffmpeg實(shí)現(xiàn)倍速播放
這篇文章主要為大家詳細(xì)介紹了在Qt音視頻開(kāi)發(fā)中如何利用ffmpeg實(shí)現(xiàn)倍速播放功能(半倍速/2倍速/4倍速/8倍速),感興趣的小伙伴可以了解一下2022-11-11C語(yǔ)言實(shí)現(xiàn)線性表的基本操作詳解
線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列,這篇文章帶你學(xué)習(xí)如何通過(guò)C語(yǔ)言實(shí)現(xiàn)線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)2021-11-11C語(yǔ)言中pthread_exit()函數(shù)實(shí)現(xiàn)終止線程
本文主要介紹了C語(yǔ)言中pthread_exit()函數(shù)實(shí)現(xiàn)終止線程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05C++ 強(qiáng)制類(lèi)型轉(zhuǎn)換詳解
這篇文章主要介紹的是C++ 強(qiáng)制類(lèi)型轉(zhuǎn)換詳解,C語(yǔ)言中的強(qiáng)制轉(zhuǎn)換主要用于普通數(shù)據(jù)類(lèi)型、指針的強(qiáng)制轉(zhuǎn)換,沒(méi)有類(lèi)型檢查,轉(zhuǎn)換不安全,下面我們來(lái)看看其具體語(yǔ)法及詳細(xì)內(nèi)容2021-11-11C 語(yǔ)言關(guān)于聯(lián)合體的相關(guān)知識(shí)
這篇文章主要介紹了C 語(yǔ)言關(guān)于聯(lián)合體的相關(guān)知識(shí),文中講解非常細(xì)致,代碼幫助大家更好的理解學(xué)習(xí),感興趣的朋友可以了解下2020-06-06C++ 中類(lèi)的拷貝、賦值、銷(xiāo)毀的實(shí)例詳解
這篇文章主要介紹了C++ 中類(lèi)的拷貝、賦值、銷(xiāo)毀的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家,需要的朋友可以參考下2017-09-09C語(yǔ)言詳解結(jié)構(gòu)體的內(nèi)存對(duì)齊與大小計(jì)算
C 數(shù)組允許定義可存儲(chǔ)相同類(lèi)型數(shù)據(jù)項(xiàng)的變量,結(jié)構(gòu)是 C 編程中另一種用戶(hù)自定義的可用的數(shù)據(jù)類(lèi)型,它允許你存儲(chǔ)不同類(lèi)型的數(shù)據(jù)項(xiàng),本篇讓我們來(lái)了解C 的結(jié)構(gòu)體內(nèi)存對(duì)齊與計(jì)算大小2022-04-04C語(yǔ)言楊氏矩陣簡(jiǎn)單實(shí)現(xiàn)方法
楊氏矩陣是一個(gè)數(shù)字矩陣,矩陣的每一行從左到右一次遞增,矩陣從上到下遞增,在這樣的矩陣中查找一個(gè)數(shù)字是否存在。時(shí)間復(fù)雜度小于O(N),有需要的朋友可以借鑒參考下2023-02-02