常用的位運算技巧

位運算是很多演算法優化的基礎和實現的條件，極其重要。理解位運算對於一些演算法及其優化有著非常重要的意義。本篇隨筆講解位運算的一些基本原理和常用的使用技巧。

基礎知識

對於位運算，大家都很熟悉，基本的位操作有與(&&)、或(||)、非(!)、異或(&)等等。在面試中經常會出現位運算相關的題，所以我就做了簡單的整理，參考了很多寫得很好的部落格及書籍,在此一併謝過。

現在簡單說一下，移位運算。

左移運算：x << y。將x左移y位，將x最左邊的y位丟棄，在右邊補y個0。

右移運算：x >> y。將x右移y位，這需要區分x是有符號數還是無符號數。在x是無符號數時，只需將x的最右邊的y位丟棄，在左邊補上y個0。在x是有符號數時，又分為x是正數還是負數。正數時，同無符號數的處理相同；負數時，將將x的最右邊的y位丟棄，在左邊補上y個1。

注：本篇隨筆的所有「運算」均指二進位制下的運算，請大家自行理解。

1、與(&)運算

(1)運演算法則

兩個二進位制數進行與&運算，如果對應位都為1則結果為1，否則為0.

(2)技巧及用途

與運算常常用於二進位制下的取位操作。想要知道二進位制下的某位是否是1，就&上這個位數對應的十進位制數。假如返回的是這個十進位制數本身，則這個位的確是1，反之就是0.

比如：

我們要取第三位是否為1，我們只需要與&上第三位（二進位制表示為100）對應的二進位制數4，如果返回值為4，就代表第三位為1，反之就是0.

最常用的是取二進位制下的最末位，即a&1。這樣的技巧可以用於判斷奇偶，根據二進位制常識，尾數為1則為奇數，反之為偶數。

2、或(|)運算

兩個二進位制數進行或|運算，如果對應位有一個為1，結果就為1.只有在兩個數的對應位置都是0的時候，結果才為0.

或運算常用於二進位制特定位的賦值。想把哪個位強行變成1，就用這個數|上這個位數對應的二進位制數。

還是上面那個例子，我們想讓00000的第三位變成1.即十進位制變4，我們直接|上4就可以。

當然，不同於&運算，我們很少用|運算進行任意位賦值。通常來講，我們只使用a|1把a的最後一位強行變成1，其實質意義是把原數加一。或者使用a|1-1再把它變為0.這個技巧通常用於把它變成它最接近的偶數。

3、異或(^)(xor)運算

兩個二進位制數進行異或(^)運算，如果對應位相同，不管是0或者是1，都返回1，反之返回0.

其實沒啥用途...

好吧，我介紹一個性質：一個數經過兩次異或之後等於原數。

（很好理解）

4、非(~)運算

把給定二進位制數全部取反。

其實沒什麼運算上的用途，本蒟蒻曾看見一些大佬用這個運算判斷輸入是否為0...

大約長這個樣子：

while(~scanf("%d",&n))

5、左移(<<)運算

a<<b表示把a的二進位制位向左移動b位，低位用0補上。

根據二進位制的常識，我們會發現，二進位制第k位上的數就等於2k。（從0開始計位）

比如，二進位制下的100就是2k=2=4。

所以我們發現，左移運算a<<b的實質就是a×2b。

左移運算最常用的技巧就是用來代替×2的整數次冪的乘法運算。因為我們普遍認為，位運算是要比四則運算加減乘除及模運算更快一些的運算。

6、右移(>>)運算

a>>b就是把a的二進位制位向右移動b位，溢位的捨去。

類比於左移運算，我們發現右移運算就是把a除以2的整數次冪。這就是右移運算的用途——優化除法運算。

這裡需要特殊說明的是，右移演算法可以用在數學知識中的求最大公約數的程式塊上。因為mod運算的效率慢的出奇，所以我們可以用右移運算來進行除以2的操作。據說可以提高百分之60的效率。

7、位運算優先順序

位運算的優先順序是我們在處理位運算的時候常常要考慮的問題，誠然，我們可以用括號強制位運算的順序，但是，我們還是應該學會位運算的優先順序（這應該是常識）。

位運算的優先順序如下：

按位反（~）>位移運算（<<,>>）>按位與（&）>按位異或（^）>按位或（|）

附：位運算在狀壓DP的用法

眾所周知，狀壓DP就是把狀態壓縮成一個01串（其實就是一個二進位制數），用以減少DP陣列的維數。但是我們在DP的時候就要按照01串來進行狀態的轉移。所以位運算是狀壓DP的基礎知識和必備知識。所以我在本篇隨筆的末尾還附上了狀壓DP中比較常用的操作及其二進位制實現的方式。

正文：（本文中的a表示十進位制下的整數）

1、獲得第i位的數字：(a>>i)&1 或者 a&(1<<i)

很好理解，我們知道可以用&1來提取最後一位的數，那麼我們現在要提取第i位數，就直接把第i位數變成最後一位即可（直接右移）。或者，我們可以直接&上1左移i位，也能達到我們的目的。

2、設定第i位為1：a=a|(1<<i)

我們知道強制賦值用|運算，所以就直接強制|上第i位即可。

3、設定第i位為0：a=a&(~(1<<i))

這裡比較難以理解。其實很簡單，我們知道非~運算是按位取反，(1<<i)非一下就變成了第i為是0，其它全是1的二進位制串。這樣再一與原數進行&運算，原數的第i位無論是什麼都會變成0，而其他位不會改變（實在不明白的可以用紙筆進行推演）。

4、把第i位取反：a=a^(1<<i)

1左移i位之後再進行異或，我們就會發現，如果原數第i位是0，一異或就變成1，否則變成0。

5、取出一個數的最後一個1：a&(-a)

學過樹狀陣列的同學會發現，這就是樹狀陣列的lowbit。事實上，這和樹狀陣列的原理是一樣的。我想，不需要我多解釋。