C++中的位運算和位圖bitmap解析
位運算總結(jié)
移位運算
- 移位運算是雙目運算符,兩個運算分量都是整形,結(jié)果也是整形。
- “<<” 左移:右邊空出的位上補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)+(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))//無符號x,y比較 x<=y: (~x|y)&((x^y)|~(y-x))//無符號x,y比較
位運算應(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ù)的平均值
對于兩個整數(shù)x,y,如果用 (x+y)/2 求平均值,會產(chǎn)生溢出,因為 x+y 可能會大于INT_MAX,但是我們知道它們的平均值是肯定不會溢出的,我們用如下算法:
int average(int x, int y) //返回X,Y 的平均值 { return (x&y)+((x^y)>>1); }
(8)判斷一個整數(shù)是不是2的冪,對于一個數(shù) x >= 0,判斷他是不是2的冪
bool power2(int x) { return ((x&(x-1))==0)&&(x!=0); }
(9)不用 temp交換兩個整數(shù),可以是負整數(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) 計算絕對值
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) 取模運算轉(zhuǎn)化成位運算 (在不產(chǎn)生溢出的情況下)
a % (2^n) 等價于 a & (2^n - 1)
(12)乘法運算轉(zhuǎn)化成位運算 (在不產(chǎn)生溢出的情況下)
a * (2^n) 等價于 a<< n
(13)除法運算轉(zhuǎn)化成位運算 (在不產(chǎn)生溢出的情況下)
a / (2^n) 等價于 a>> n 例: 12/8 == 12>>3
(14) a % 2 等價于 a & 1
(15) x 的 相反數(shù) 表示為 (~x+1)
(16)兩整數(shù)相加,可以是負整數(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億個不重復(fù)的無符號整數(shù),沒排過序。給一個無符號整數(shù),如何快 速判斷一個數(shù)是否在這40億個數(shù)中。 【騰訊】
思路:
這道題首先要判斷40億個不重復(fù)的無符號整數(shù)究竟占多大的內(nèi)存,因為太大的內(nèi)存我們無法加載到現(xiàn)有的計算機中。
一個整數(shù)是4個字節(jié),40億個整數(shù)就是160億個字節(jié),也就相當于16G內(nèi)存,就一般的計算機而言很難實現(xiàn)這個加載,所以我們可以采取以下兩種方案,一種是分割,一種是位圖。
方法:
①分割
采用分割處理,把40億個數(shù)分批次處理完畢,當然可以實現(xiàn)我們最終的目標,但是這樣做時間復(fù)雜度未免優(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)代碼:
#include <iostream> #include <vector> using namespace std; class BitMap { public: BitMap(size_t range) { //此時多開辟一個空間 _bits.resize(range / 32 + 1); } void Set(size_t x) { int index = x / 32;//確定哪個數(shù)據(jù)(區(qū)間) int temp = x % 32;//確定哪個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; }
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
實例講解在C++的函數(shù)中變量參數(shù)及默認參數(shù)的使用
這篇文章主要介紹了在C++的函數(shù)中變量參數(shù)及默認參數(shù)的使用,是C++函數(shù)入門學(xué)習中的基礎(chǔ)知識,需要的朋友可以參考下2016-01-01輸入一個字符串,取出其中的整數(shù)(實現(xiàn)代碼)
輸入一個字符串,內(nèi)含所有數(shù)字和非數(shù)字字符。將其中連續(xù)的數(shù)字作為一個整數(shù),依次存放到一個數(shù)組中,統(tǒng)計共有多少個整數(shù),并輸出這些數(shù)2013-09-09