欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中的位運算和位圖bitmap解析

 更新時間:2022年07月22日 16:23:46   作者:CW96  
這篇文章主要介紹了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語言的分支和循環(huán)語句你真的了解嗎

    C語言的分支和循環(huán)語句你真的了解嗎

    這篇文章主要為大家詳細介紹了C語言的分支和循環(huán)語句,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-02-02
  • 實例講解在C++的函數(shù)中變量參數(shù)及默認參數(shù)的使用

    實例講解在C++的函數(shù)中變量參數(shù)及默認參數(shù)的使用

    這篇文章主要介紹了在C++的函數(shù)中變量參數(shù)及默認參數(shù)的使用,是C++函數(shù)入門學(xué)習中的基礎(chǔ)知識,需要的朋友可以參考下
    2016-01-01
  • C++模版函數(shù)詳解

    C++模版函數(shù)詳解

    C++中的模版總體可以分為兩大類:模版函數(shù)、模版類。本篇文章先寫模版函數(shù),需要的朋友可以參考下
    2017-02-02
  • 輸入一個字符串,取出其中的整數(shù)(實現(xiàn)代碼)

    輸入一個字符串,取出其中的整數(shù)(實現(xiàn)代碼)

    輸入一個字符串,內(nèi)含所有數(shù)字和非數(shù)字字符。將其中連續(xù)的數(shù)字作為一個整數(shù),依次存放到一個數(shù)組中,統(tǒng)計共有多少個整數(shù),并輸出這些數(shù)
    2013-09-09
  • strcpy函數(shù)實現(xiàn)簡示例命分享

    strcpy函數(shù)實現(xiàn)簡示例命分享

    這篇文章主要介紹了strcpy函數(shù)實現(xiàn)簡示例命,需要的朋友可以參考下
    2014-03-03
  • Matlab繪制雨云圖的方法詳解

    Matlab繪制雨云圖的方法詳解

    這篇文章主要介紹了如何利用Matlab實現(xiàn)雨云圖的繪制,文中的示例代碼講解詳細,對我們學(xué)習Matlab有一定的幫助,需要的可以參考一下
    2022-05-05
  • C語言文件操作詳解

    C語言文件操作詳解

    這篇文章主要介紹了C語言 文件操作解析詳解及實例代碼的相關(guān)資料,需要的朋友可以參考下,希望能夠給你帶來幫助
    2021-10-10
  • C++實現(xiàn)順序表的常用操作(插入刪出查找輸出)

    C++實現(xiàn)順序表的常用操作(插入刪出查找輸出)

    實現(xiàn)順序表的插入,刪除,查找,輸出操作在C語言中經(jīng)常用到。下面小編給大家整理實現(xiàn)代碼,一起看下吧
    2016-08-08
  • OpenCV實現(xiàn)拼接圖像的簡單方法

    OpenCV實現(xiàn)拼接圖像的簡單方法

    這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)拼接圖像的簡單方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-05-05
  • C語言中的5種簡單排序算法(適合小白)

    C語言中的5種簡單排序算法(適合小白)

    在編程練習時我們經(jīng)常會遇到一些將一串亂序的數(shù)字排列成有序的數(shù)列(遞增,遞減)的問題,以此起到解決問題的效果,下面這篇文章主要給大家介紹了關(guān)于C語言中的5種簡單排序算法的相關(guān)資料,需要的朋友可以參考下
    2023-03-03

最新評論