C++中的位運(yùn)算和位圖bitmap解析
位運(yùn)算總結(jié)
移位運(yùn)算
- 移位運(yùn)算是雙目運(yùn)算符,兩個(gè)運(yùn)算分量都是整形,結(jié)果也是整形。
- “<<” 左移:右邊空出的位上補(bǔ)0,左邊的位將從首位擠掉,其值相當(dāng)于乘2。
- ">>"右移:右邊的位被擠掉。對(duì)于左邊移出的空位,如果是正數(shù)則空位補(bǔ)0,若為負(fù)數(shù),可能補(bǔ)0或補(bǔ)1,這取決于所用的計(jì)算機(jī)系統(tǒng)。
二進(jìn)制補(bǔ)碼運(yùn)算公式:
-x = ~x + 1 = ~(x-1) -(~x) = x+1 ~(-x) = x-1 x+y = x - ~y - 1 = (x|y)+(x&y) x-y = x + ~y + 1 = (x|~y)-(~x&y) x^y = (x|y)-(x&y) x|y = (x&~y)+y x&y = (~x|y)-~x x==y: ~(x-y|y-x) x!=y: x-y|y-x x< y: (x-y)^((x^y)&((x-y)^x)) x<=y: (x|~y)&((x^y)|~(y-x)) x< y: (~x&y)|((~x|y)&(x-y))//無符號(hào)x,y比較 x<=y: (~x|y)&((x^y)|~(y-x))//無符號(hào)x,y比較
位運(yùn)算應(yīng)用舉例
(1) 判斷int型變量a是奇數(shù)還是偶數(shù)
a&1 = 0 偶數(shù) a&1 = 1 奇數(shù)
(2) 取int型變量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1
(3) 將int型變量a的第k位清0,即
a = a&~(1<<k)
(4) 將int型變量a的第k位置1,
a=a|(1<<k)
(5) int型變量循環(huán)左移k次,
a=a<<k|a>>sizeof(unsigned int)*8-k
(6) int型變量a循環(huán)右移k次,
a=a>>k|a<<sizeof(unsigned int)*8-k
(7) 整數(shù)的平均值
對(duì)于兩個(gè)整數(shù)x,y,如果用 (x+y)/2 求平均值,會(huì)產(chǎn)生溢出,因?yàn)?x+y 可能會(huì)大于INT_MAX,但是我們知道它們的平均值是肯定不會(huì)溢出的,我們用如下算法:
int average(int x, int y) //返回X,Y 的平均值 { return (x&y)+((x^y)>>1); }
(8)判斷一個(gè)整數(shù)是不是2的冪,對(duì)于一個(gè)數(shù) x >= 0,判斷他是不是2的冪
bool power2(int x) { return ((x&(x-1))==0)&&(x!=0); }
(9)不用 temp交換兩個(gè)整數(shù),可以是負(fù)整數(shù)
void swap( int& x , int& y) { x ^= y; y ^= x; x ^= y; } void swap01(int& x , int& y){ x += y; y = x - y; x = x - y; }
(10) 計(jì)算絕對(duì)值
int abs( int x ) { int y ; y = x >> 31 ; return (x^y)-y ; //or: (x+y)^y } int abs01(int a){ return (a>0)?a:(~a+1); }
(11) 取模運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下)
a % (2^n) 等價(jià)于 a & (2^n - 1)
(12)乘法運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下)
a * (2^n) 等價(jià)于 a<< n
(13)除法運(yùn)算轉(zhuǎn)化成位運(yùn)算 (在不產(chǎn)生溢出的情況下)
a / (2^n) 等價(jià)于 a>> n 例: 12/8 == 12>>3
(14) a % 2 等價(jià)于 a & 1
(15) x 的 相反數(shù) 表示為 (~x+1)
(16)兩整數(shù)相加,可以是負(fù)整數(shù)
int add(int a,int b){ while(b!=0){ int temp=a^b; b=(unsigned int)(a&b)<<1; a = temp; } return a; }
位圖
題目:
給40億個(gè)不重復(fù)的無符號(hào)整數(shù),沒排過序。給一個(gè)無符號(hào)整數(shù),如何快 速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中。 【騰訊】
思路:
這道題首先要判斷40億個(gè)不重復(fù)的無符號(hào)整數(shù)究竟占多大的內(nèi)存,因?yàn)樘蟮膬?nèi)存我們無法加載到現(xiàn)有的計(jì)算機(jī)中。
一個(gè)整數(shù)是4個(gè)字節(jié),40億個(gè)整數(shù)就是160億個(gè)字節(jié),也就相當(dāng)于16G內(nèi)存,就一般的計(jì)算機(jī)而言很難實(shí)現(xiàn)這個(gè)加載,所以我們可以采取以下兩種方案,一種是分割,一種是位圖。
方法:
①分割
采用分割處理,把40億個(gè)數(shù)分批次處理完畢,當(dāng)然可以實(shí)現(xiàn)我們最終的目標(biāo),但是這樣做時(shí)間復(fù)雜度未免優(yōu)點(diǎn)太高。
②位圖BitMap
在介紹這種方法前我首先來介紹一下什么是位圖。
位圖BitMap:位圖是一個(gè)數(shù)組的每一個(gè)數(shù)據(jù)的每一個(gè)二進(jìn)制位表示一個(gè)數(shù)據(jù),0表示數(shù)據(jù)不存在,1表示數(shù)據(jù)存在。
如上所示,當(dāng)我們需要存放一個(gè)數(shù)據(jù)的時(shí)候,我們需要安裝以下方法:
首先確定這個(gè)數(shù)字在整個(gè)數(shù)據(jù)的哪一個(gè)數(shù)據(jù)(區(qū)間)。
確定這個(gè)數(shù)據(jù)(區(qū)間)的哪一個(gè)Bit位上。
在這個(gè)位上置1即可。
實(shí)現(xiàn)代碼:
#include <iostream> #include <vector> using namespace std; class BitMap { public: BitMap(size_t range) { //此時(shí)多開辟一個(gè)空間 _bits.resize(range / 32 + 1); } void Set(size_t x) { int index = x / 32;//確定哪個(gè)數(shù)據(jù)(區(qū)間) int temp = x % 32;//確定哪個(gè)Bit位 _bits[index] |= (1 << temp);//位操作即可 } void Reset(size_t x) { int index = x / 32; int temp = x % 32; _bits[index] &= ~(1 << temp);//取反 } bool Test(size_t x) { int index = x / 32; int temp = x % 32; if (_bits[index]&(1<<temp)) return 1; else return 0; } private: vector<int> _bits; }; void TestBitMap() { BitMap am(-1); BitMap bm(200); bm.Set(136); bm.Set(1); cout << bm.Test(136) << endl; bm.Reset(136); cout << bm.Test(136) << endl; } int main() { TestBitMap(); return 0; }
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
相關(guān)文章
實(shí)例講解在C++的函數(shù)中變量參數(shù)及默認(rèn)參數(shù)的使用
這篇文章主要介紹了在C++的函數(shù)中變量參數(shù)及默認(rèn)參數(shù)的使用,是C++函數(shù)入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01輸入一個(gè)字符串,取出其中的整數(shù)(實(shí)現(xiàn)代碼)
輸入一個(gè)字符串,內(nèi)含所有數(shù)字和非數(shù)字字符。將其中連續(xù)的數(shù)字作為一個(gè)整數(shù),依次存放到一個(gè)數(shù)組中,統(tǒng)計(jì)共有多少個(gè)整數(shù),并輸出這些數(shù)2013-09-09strcpy函數(shù)實(shí)現(xiàn)簡示例命分享
這篇文章主要介紹了strcpy函數(shù)實(shí)現(xiàn)簡示例命,需要的朋友可以參考下2014-03-03C++實(shí)現(xiàn)順序表的常用操作(插入刪出查找輸出)
實(shí)現(xiàn)順序表的插入,刪除,查找,輸出操作在C語言中經(jīng)常用到。下面小編給大家整理實(shí)現(xiàn)代碼,一起看下吧2016-08-08