枚舉查找和對分查找的優劣

枚舉查找的劣勢簡直無需多言，有n個元素，那復雜度就是o(n)，查找一個元素是如此地費勁！倘若我需要你做m次查找，復雜度就是o(n*m)。當然，我們可以用對分查找來優化，但是對分查找需要一個有序的數組，通過每次對折一半的方法，最終的復雜度是o(logn)，小于線性。但是這還是不能讓我們滿意。
在解決圖論問題時，我們用到了DFS。DFS要求不能經過重復的點，所以我們需要創建一個數組來記錄走過的點，那么我們DFS到一個點時會用查找算法么…
寫一個for循環…遍歷整個數組？還是說，加入一個元素就來一個排序，最后用對分？線段樹？

哈希散列表

別看這名字專業，其實這是一個很常用的技巧。
使用這種方法，可以使查找一個元素的復雜度變為o(1)。真的是o(1)！！！
在做DFS的時候，為了標記這個點有沒有被搜索過，我們會用一個bool類型的數組vis來記錄搜到的每一個點，我們如果搜到了點5，那就記錄vis[5]=true（初始化都是false）。所以我們下次搜到一個點，比如搜到了點5，我們只需要if(vis[5])就好了。如果是true，就說明被搜過。
這是典型的犧牲空間換時間的做法（回憶一下桶排序）
當然，代價是你需要很大的空間來滿足。
因此真正的哈希散列表還會對存入的元素取模，這里不細講，但是，不論他怎么取模，都不會勝過我們接下來要講的神奇的數組——比特數組！
在此之前，先普及一個知識：位運算

位運算

我給你一個提綱吧。
每一個數都有自己的二進制，計算機中，一個1或者0的二進制位都是占1byte（比特）的。一個int變量最大可以存到21億，所以她的二進制位差不多有32個，占4kb左右。比如一個int類型的1，它在計算機的二進制里就是00000000000000000000000000000001，前面有31個0！
設二進制數a=1101,b=1001

• ！是按位取反的意思，就是把a的每一位二進制位都取反，例如1取反就是0。所以！a=0010那就是10
• ~是數字取負，在加法中的應用如 ~11-1=-11-1=-12
• ^是按位異或，說道這個，曾幾何時，千萬C++初學者在寫一道題目：計算平面上兩點的距離時，統統把
  “ ^”符號當做平方……然后不停地抱怨著編譯器出問題了……然而這個符號其實是這么用滴：就是兩個數對應的二進制位相同的時候，就變成0，否則是1，例如a ^b，結果是0100也就是100的意思，a和b的第二位不同，所以變1。
• &這個是按位與，也就是說兩個數對應的二進制位都是1的時候，結果的二進制位才會是1，否則是0，例如a&b，結果是1001。這個符號有一個妙用，比如c&1=1時，c是奇數，c&1=0時，c是偶數。因為奇數的最后一位二進制必然是1，所以和1相與，結果就會是1。（1可以看做0000001,前面有31個0）
• | 這個是按位或。兩個數對應的二進制位只要有一個，兩個數隨便哪一個是1的時候，結果的二進制位是1，否則是0。如a | b，結果是1101
• <<這個是左移符號，就是把所有的1都往左移。移出來的位由0來補上。比如101<<2，就是把101左移兩位，假如我們限制它的二進制位長度只能為3，那么移動結果就是100。
• 和左移相反的是右移,就是這個>>，就是把所有的1都往右移。移出來的位由0來補上。比如101>>2,假如我們限制它的二進制位長度只能為3，那么移動結果就是001。就是1。

比特數組

這個數組也是一個int類型數組，然而它一個單位可以儲存31個數。比如說a[1]可以存31個數字！
我們已經知道，一個int可以存32個2進制位，那么我們可以把每一個2進制位都利用起來存儲數據！比如一個int的第24個二進制位我們設置為1，就代表存在24這個數了，是不是跟上文的vis很像呢？
我們這么存儲一個數據：

void addnum(int x){data[x/32]|=1<<(x%32);return; }

正如我們所言，每一個data對應的存儲單位都可以達到31個。
當我們讀入40的時候，它會存在data[1]中，存在data[1]中的第八位。那么他就左移8位，也就是把這個1放到第八位上。然后取或運算，保留了原來的數據，原來里面存的1還是1。
然后我們這樣讀取一個數據：

bool find(int x){return data[x/32]>>(x%32)&1; }

確切的說是詢問這個數存在與否。例如我們詢問40，那么他就會找到data[1]，右移那么多位然后與一個1，如果真的存在這個數，那與的結果必然是1，也就是返回了true了。
完整代碼：

#include<iostream> using namespace std; #define maxm 10001 int data[maxm],n,m,num;void addnum(int x){data[x/32]|=1<<(x%32);return; }bool find(int x){return data[x/32]>>(x%32)&1; }int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>num;addnum(num);}if(find(m)) cout<<"yes";else cout<<"no";return 0; }

總結

以上是生活随笔為你收集整理的位运算和比特数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。