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比較
位運算應用舉例
(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億個不重復的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快 速判斷一個數(shù)是否在這40億個數(shù)中。 【騰訊】
思路：
這道題首先要判斷40億個不重復的無符號整數(shù)究竟占多大的內(nèi)存，因為太大的內(nèi)存我們無法加載到現(xiàn)有的計算機中。
一個整數(shù)是4個字節(jié)，40億個整數(shù)就是160億個字節(jié)，也就相當于16G內(nèi)存，就一般的計算機而言很難實現(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)代碼：
#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)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
C語言三種函數(shù)調(diào)用約定_cdecl與_stdcall及_fastcall詳細講解
本篇文章使用的工具是vs2010，內(nèi)容可能涉及到匯編的知識，建議有一些匯編基礎的再來看，不過沒有匯編基礎也沒有關系，了解一下這三種調(diào)用約定即可2022-10-10
線程間如何通信同步？一些伙伴好奇線程間的通信及同步方法，沒關系，下面小編就繼續(xù)給大家科普下線程間通信及同步的方法以及互斥量2022-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)數(shù)字游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
這篇文章主要介紹了EasyC++自動存儲持續(xù)性，下面文章圍繞EasyC++自動存儲持續(xù)性的相關資料展開全文資料，需要的小伙伴可以參考一下下面文章的具體內(nèi)容，希望對你的學習有所幫助2021-12-12
這篇文章主要介紹了C語言獲取消耗內(nèi)存的方法,涉及C語言中malloc方法的使用技巧,非常簡單實用,需要的朋友可以參考下2015-07-07
C語言實現(xiàn)學生信息管理系統(tǒng)開發(fā)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)學生信息管理系統(tǒng)開發(fā)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了C++類的定義與實現(xiàn)，違章圍繞C++類的定義的相關資料展開全文內(nèi)容，具有一定的參考價值，需要的小伙伴可以參考一下2022-01-01
本文介紹了“C++讀寫.mat文件的方法”，需要的朋友可以參考一下2013-03-03
這篇文章主要介紹了C++之set自定義排序問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
這篇文章主要為大家詳細介紹了C++實現(xiàn)景區(qū)信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01