第C++中的位運算和位圖bitmap解析目錄位運算總結移位運算位運算應用舉例位圖

位運算總結

移位運算

移位運算是雙目運算符，兩個運算分量都是整形，結果也是整形。左移：右邊空出的位上補0，左邊的位將從首位擠掉，其值相當于乘2。右移：右邊的位被擠掉。對于左邊移出的空位，如果是正數(shù)則空位補0，若為負數(shù)，可能補0或補1，這取決于所用的計算機系統(tǒng)。

二進制補碼運算公式：

-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))//無符號x,y比較

x=y:(~x|y)((x^y)|~(y-x))//無符號x,y比較

位運算應用舉例

(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ù)的平均值

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

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

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

}

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

boolpower2(intx)

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

}

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

voidswap(intx,inty)

x^=y;

y^=x;

x^=y;

voidswap01(intx,inty）{

x+=y;

y=x-y;

x=x-y;

}

(10)計算絕對值

intabs(intx)

inty;

y=x31;

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

intabs01(inta){

return(a0)a:(~a+1);

}

(11)取模運算轉化成位運算(在不產生溢出的情況下)

a%(2^n)等價于a(2^n-1)

(12)乘法運算轉化成位運算(在不產生溢出的情況下)

a*(2^n)等價于an

(13)除法運算轉化成位運算(在不產生溢出的情況下)

a/(2^n)等價于an

例:12/8==123

(14)a%2等價于a1

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

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

intadd(inta,intb){

while(b!=0){

inttemp=a^b;

b=(unsignedint)(ab)1;

a=temp;

returna;

}

位圖

題目：

給40億個不重復的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中。【騰訊】

思路：

這道題首先要判斷40億個不重復的無符號整數(shù)究竟占多大的內存，因為太大的內存我們無法加載到現(xiàn)有的計算機中。

一個整數(shù)是4個字節(jié)，40億個整數(shù)就是160億個字節(jié)，也就相當于16G內存，就一般的計算機而言很難實現(xiàn)這個加載，所以我們可以采取以下兩種方案，一種是分割，一種是位圖。

方法：

①分割

采用分割處理，把40億個數(shù)分批次處理完畢，當然可以實現(xiàn)我們最終的目標，但是這樣做時間復雜度未免優(yōu)點太高。

②位圖BitMap

在介紹這種方法前我首先來介紹一下什么是位圖。

位圖BitMap：位圖是一個數(shù)組的每一個數(shù)據(jù)的每一個二進制位表示一個數(shù)據(jù)，0表示數(shù)據(jù)不存在，1表示數(shù)據(jù)存在。

如上所示，當我們需要存放一個數(shù)據(jù)的時候，我們需要安裝以下方法：

首先確定這個數(shù)字在整個數(shù)據(jù)的哪一個數(shù)據(jù)（區(qū)間）。

確定這個數(shù)據(jù)（區(qū)間）的哪一個Bit位上。

在這個位上置1即可。

實現(xiàn)代碼：

#includeiostream

#includevector

usingnamespacestd;

classBitMap

public:

BitMap(size_trange)

//此時多開辟一個空間

_bits.resize(range/32+1);

voidSet(size_tx)

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

inttemp=x%32;//確定哪個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)