C++中的位運(yùn)算和位圖bitmap解析

第C++中的位運(yùn)算和位圖bitmap解析目錄位運(yùn)算總結(jié)移位運(yùn)算位運(yùn)算應(yīng)用舉例位圖

位運(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)+(xy)

x-y=x+~y+1=(x|~y)-(~xy)

x^y=(x|y)-(xy)

x|y=(x~y)+y

xy=(~x|y)-~x

x==y:~(x-y|y-x)

x!=y:x-y|y-x

xy:(x-y)^((x^y)((x-y)^x))

x=y:(x|~y)((x^y)|~(y-x))

xy:(~xy)|((~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ù)

a1=0偶數(shù)

a1=1奇數(shù)

(2)取int型變量a的第k位(k=0,1,2sizeof(int))，即ak1

(3)將int型變量a的第k位清0，即

a=a~(1k)

(4)將int型變量a的第k位置1，

a=a|(1k)

(5)int型變量循環(huán)左移k次，

a=ak|asizeof(unsignedint)*8-k

(6)int型變量a循環(huán)右移k次，

a=ak|asizeof(unsignedint)*8-k

(7)整數(shù)的平均值

對(duì)于兩個(gè)整數(shù)x,y，如果用(x+y)/2求平均值，會(huì)產(chǎn)生溢出，因?yàn)閤+y可能會(huì)大于INT_MAX，但是我們知道它們的平均值是肯定不會(huì)溢出的，我們用如下算法：

intaverage(intx,inty)//返回X,Y的平均值

return(xy)+((x^y)1);

}

(8)判斷一個(gè)整數(shù)是不是2的冪,對(duì)于一個(gè)數(shù)x=0，判斷他是不是2的冪

boolpower2(intx)

return((x(x-1))==0)(x!=0)；

}

(9)不用temp交換兩個(gè)整數(shù),可以是負(fù)整數(shù)

voidswap(intx,inty)

x^=y;

y^=x;

x^=y;

voidswap01(intx,inty）{

x+=y;

y=x-y;

x=x-y;

}

(10)計(jì)算絕對(duì)值

intabs(intx)

inty;

y=x31;

return(x^y)-y;//or:(x+y)^y

intabs01(inta){

return(a0)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à)于an

(13)除法運(yùn)算轉(zhuǎn)化成位運(yùn)算(在不產(chǎn)生溢出的情況下)

a/(2^n)等價(jià)于an

例:12/8==123

(14)a%2等價(jià)于a1

(15)x的相反數(shù)表示為(~x+1)

(16)兩整數(shù)相加,可以是負(fù)整數(shù)

intadd(inta,intb){

while(b!=0){

inttemp=a^b;

b=(unsignedint)(ab)1;

a=temp;

returna;

}

位圖

題目：

給40億個(gè)不重復(fù)的無符號(hào)整數(shù)，沒排過序。給一個(gè)無符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中?！掘v訊】

思路：

這道題首先要判斷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)代碼：

#includeiostream

#includevector

usingnamespacestd;

classBitMap

public:

BitMap(size_trange)

//此時(shí)多開辟一個(gè)空間

_bits.resize(range/32+1);

voidSet(size_tx)

intindex=x/32;//確定哪個(gè)數(shù)據(jù)（區(qū)間）

inttemp=x%32;//確定哪個(gè)Bit位

_bits[index]|=(1temp);//位操作即可

voidReset(size_tx)

intindex=x/32;

inttemp=x%32;

_bits[index]=~(1temp);//取反

boolTest(size_tx)

intindex=x/32;

inttemp=x%32;

if(_bits[index](1temp))

return1;

else

return0;

private:

vectorint_bits;

voidTestBitMap()

BitMapam(-1);

BitMapbm(200);

bm.Set(136);

bm.Set(1)