位運算入門應用及技巧

轉載的位運算

原文戳這裡

位運算是資訊奧賽中重要的一部分，由于位運算的速度比一般運算快，掌握了位運算，就能夠在程式編寫時更加靈活，提高程式效率，對解題有十分重要的幫助。

位運算的所有操作都是建立在二進制位上的，是以在學習位運算之前，請保證熟悉了二進制的基本運算法則以及基本的邏輯與、或、非運算。

一、位運算基本操作

1、左移操作 <<

左移操作可以将二進制數a的每個數位均進行左移，并在移動後右邊空出來的數位補0。

例如：a << b意為将二進制數a左移b個數位，在右邊空出數位補0。假設a=101，b=1，則将二進制數a左移1位，右邊空出來的數位補0，是以新數為1010，同理，a=101，b=2時的新數為10100，依次類推。

需要注意的是，二進制數左移n位等于對應的十進制數 * 2^n。例如二進制數101對應的十進制數是5，則将101左移2位後得到的二進制數10100對應的十進制數為5*2^2=20。

2、右移操作 >>

與左移操作類似，右移操作可以将二進制數a的每個數位均進行右移，忽略移動後的小數數位。

例如：a >> b意為将二進制數a右移b個數位，将小數部分（移動前的後b位）删去。假設a=10101，b=2，則移動後的新數為101。

同上，二進制數右移n為等于對應的十進制數/2^n（下取整）。

3、按位與操作 &

按位與操作會将兩個二進制數的數位對齊（數位少的高位補0），之後對每一位依次進行與操作。

例如：a=111（補0後為00111），b=11110，則a&b的結果為00110。

&運算可以用來取一個數對應的二進制數的最末位，例如a&1即為a對應二進制數的最末位。二進制數最末位為0則該數為偶數，為1則為奇數。

4、按位或操作 |

與按位與操作相同，按位或操作會将兩個二進制數的數位對齊，之後對每一位依次進行或操作。

|運算常用作對某數對應的二進制數的某一位無條件指派，例如a|1即将a對應二進制數的最末位指派為1。

5、按位非操作 ~

按位非操作可以将二進制數的每一位進行非（取反）操作。

如果該數為無符号整數類，該操作會将數字後面所有的0均變為1，如果該數為有符号整數類，那麼計算機會按照補碼的法則對得到的反碼繼續進行運算，由于過程複雜，在此略去，有興趣的讀者可以自行查閱資料。（大神勿噴） 建議大家做題時盡量不要使用此操作。

6、按位異或操作 ^

按位異或操作會将兩個二進制數的數位對齊,之後對每一位進行如下規則的操作：

如果兩數該數位上的數相同（同為0或1），則得到的新數的該數位為0，否則新數該數位為1。

例如：a=00101，b=11100，則a^b的結果為11001。

按位異或操作的逆運算是它本身，也就是說a^b=c，則c^b=a。

由于某數的一個數位^0的結果不變，^1的結果取反，在程式中，位運算常用來對一個數對應的二進制數的某一位進行取反，例如a^1即将a的最末位進行取反，a^10即将a的倒數第二位進行取反。

使用位運算時注意優先級順序，如果不清楚建議用括号括起來

二、利用位運算進行狀态壓縮與子集枚舉

在諸如動态規劃的題目中，我們常常需要将目前狀态儲存下來。而利用二進制位來儲存狀态成為了一種不錯的選擇。

比如在一個狀态中有幾樣物品，有選擇了的，有沒有選擇的，我們可以用”1”表示選擇了的，用”0”表示沒選擇的，則原狀态可以表示為諸如二進制1010010的集合，它可以轉化為一個十進制數字存放在數組中，是以十分友善。而我們也可以用上面介紹的操作對其某一位快速進行指派、取值、判斷沖突、取反等操作。

有一個重要的利用位運算枚舉一個集合的子集的技巧。設集合為S，需要枚舉的子集為S0，則可以用如下循環枚舉一個集合的所有子集（不包括空集）：

for(S0=S;S0!=0;S0=(S0-1)&S)
           

掌握了這種子集枚舉方法以及用位運算對集合的操作方法，在以後遇到的此類題目中你都能十分靈活的應對，隻是要注意一點：用位運算表示集合的範圍非常小，是以當集合過大時請使用位向量法等其他方法代替二進制法表示子集。

關于位運算的講解就到這裡結束了，希望大家能夠習慣并熟練運用它，相信這一定能對解題發揮十分巨大的作用。