位運(yùn)算簡介及實(shí)用技巧（一）：基礎(chǔ)篇

1、位運(yùn)算簡介及實(shí)用技巧（一）：基礎(chǔ)篇去年年底寫的關(guān)于位運(yùn)算的日志是這個(gè)blog里少數(shù)大受歡迎的文章之一，無數(shù)人都希翼我能不斷完美那篇文章。后來我看到了不少其它的資料，學(xué)習(xí)到了更多關(guān)于位運(yùn)算的學(xué)問，有了重新收拾位運(yùn)算技巧的主意。從此天起我就開頭寫這一系列位運(yùn)算講解文章，與其說是本來那篇文章的follow-up，不如說是一個(gè)remake。固然首先我還是從最基礎(chǔ)的東西說起。什么是位運(yùn)算？ 程序中的全部數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲存的。位運(yùn)算說穿了，就是挺直對整數(shù)在內(nèi)存中的二進(jìn)制位舉行操作。比如，and運(yùn)算原來是一個(gè)規(guī)律運(yùn)算符，但整數(shù)與整數(shù)之間也可以舉行and運(yùn)算。舉個(gè)例子，6的二進(jìn)制是110，

2、11的二進(jìn)制是1011，那么6 and 11的結(jié)果就是2，它是二進(jìn)制對應(yīng)位舉行規(guī)律運(yùn)算的結(jié)果（0表示fae，1表示true，空位都當(dāng)0處理）： 110and 1011- 0010 - 2 因?yàn)槲贿\(yùn)算挺直對內(nèi)存數(shù)據(jù)舉行操作，不需要轉(zhuǎn)成十進(jìn)制，因此處理速度十分快。固然有人會說，這個(gè)快了有什么用，計(jì)算6 and 11沒有什么實(shí)際意義啊。這一系列的文章就將告知你，位運(yùn)算到底可以干什么，有些什么經(jīng)典應(yīng)用，以及如何用位運(yùn)算優(yōu)化你的程序。pascal和c中的位運(yùn)算符號 下面的a和b都是整數(shù)類型，則：c語言 | pascal語言-+-a b | a and ba | b | a or ba b | a xor

3、 b a | not aa b | a shl ba b | a shr b 注重c中的規(guī)律運(yùn)算和位運(yùn)算符號是不同的。520|1314=1834，但520|1314=1，由于規(guī)律運(yùn)算時(shí)520和1314都相當(dāng)于true。同樣的，!a和a也是有區(qū)分的。各種位運(yùn)算的用法 = 1. and運(yùn)算 = and運(yùn)算通常用于二進(jìn)制取位操作，例如一個(gè)數(shù) and 1的結(jié)果就是取二進(jìn)制的最末位。這可以用來推斷一個(gè)整數(shù)的奇偶，二進(jìn)制的最末位為0表示該數(shù)為偶數(shù)，最末位為1表示該數(shù)為奇數(shù). = 2. or運(yùn)算 = or運(yùn)算通常用于二進(jìn)制特定位上的無條件賦值，例如一個(gè)數(shù)or 1的結(jié)果就是把二進(jìn)制最末位強(qiáng)行變成1。假如需要把

4、二進(jìn)制最末位變成0，對這個(gè)數(shù)or 1之后再減一就可以了，其實(shí)際意義就是把這個(gè)數(shù)強(qiáng)行變成最臨近的偶數(shù)。 = 3. xor運(yùn)算 = xor運(yùn)算通常用于對二進(jìn)制的特定一位舉行取反操作，由于異或可以這樣定義：0和1異或0都不變，異或1則取反。 xor運(yùn)算的逆運(yùn)算是它本身，也就是說兩次異或同一個(gè)數(shù)最后結(jié)果不變，即(a xor b) xor b = a。xor運(yùn)算可以用于容易的加密，比如我想對我mm說1314520，但怕別人知道，于是雙方商定拿我的生日19880516作為密鑰。1314520 xor 19880516 = 20665500，我就把20665500告知mm。mm再次計(jì)算20665500 xo

5、r 19880516的值，得到1314520，于是她就明了了我的企圖。 下面我們看另外一個(gè)東西。定義兩個(gè)符號和（我怎么找不到那個(gè)圈里有個(gè)叉的字符），這兩個(gè)符號互為逆運(yùn)算，也就是說(x y) y = x?，F(xiàn)在依次執(zhí)行下面三條，結(jié)果是什么？x - x yy - x yx - x y 執(zhí)行了第一句后x變成了x y。那么其次句實(shí)質(zhì)就是y - x y y，因?yàn)楹突槟孢\(yùn)算，那么此時(shí)的y變成了本來的x。第三句中x事實(shí)上被賦值為(x y) x，假如運(yùn)算具有交換律，那么賦值后x就變成最初的y了。這三句話的結(jié)果是，x和y的位置互換了。 加法和減法互為逆運(yùn)算，并且加法滿足交換律。把換成+，把換成-，我們可以寫出一

6、個(gè)不需要暫時(shí)變量的swap過程(pascal)。procere swap(var a,b:longint);begin a:=a + b; b:=a - b; a:=a - b;end; 好了，剛才不是說xor的逆運(yùn)算是它本身嗎？于是我們就有了一個(gè)看起來十分詭異的swap過程：procure swap(var a,b:longint);begin a:=a xor b; b:=a xor b; a:=a xor b;end; = 4. not運(yùn)算 = not運(yùn)算的定義是把內(nèi)存中的0和1所有取反。用法not運(yùn)算時(shí)要分外當(dāng)心，你需要注重整數(shù)類型有沒有符號。假如not的對象是無符號整數(shù)（不能表示負(fù)數(shù)

7、），那么得到的值就是它與該類型上界的差，由于無符號類型的數(shù)是用$0000到$ffff依次表示的。下面的兩個(gè)程序（僅語言不同）均返回65435。var a:word;begin a:=100; a:=not a; (a);end.ilude stdio.h int main() unsigned short a=100; a = a; printf( %dn, a ); return 0; 假如not的對象是有符號的整數(shù)，狀況就不一樣了，稍后我們會在 整數(shù)類型的儲存 小節(jié)中提到。 = 5. shl運(yùn)算 = a shl b就表示把a(bǔ)轉(zhuǎn)為二進(jìn)制后左移b位（在后面添b個(gè)0）。例如100的二進(jìn)制為110

8、0100，而110010000轉(zhuǎn)成十進(jìn)制是400，那么100 shl 2 = 400?？梢钥闯觯琣 shl b的值事實(shí)上就是a乘以2的b次方，由于在二進(jìn)制數(shù)后添一個(gè)0就相當(dāng)于該數(shù)乘以2。 通常認(rèn)為a shl 1比a * 2更快，由于前者是更底層一些的操作。因此程序中乘以2的操作請盡量用左移一位來代替。 定義一些常量可能會用到shl運(yùn)算。你可以便利地用1 shl 16 - 1來表示65535。無數(shù)算法和數(shù)據(jù)結(jié)構(gòu)要求數(shù)據(jù)規(guī)模必需是2的冪，此時(shí)可以用shl來定義max_n等常量。 = 6. shr運(yùn)算 = 和shl相像，a shr b表示二進(jìn)制右移b位（去掉末b位），相當(dāng)于a除以2的b次方（取整）。

9、我們也常常用shr 1來代替div 2，比如二分查找、堆的插入操作等等。想方法用shr代替除法運(yùn)算可以使程序效率大大提高。最大公約數(shù)的二進(jìn)制算法用除以2操作來代替慢得出奇的mod運(yùn)算，效率可以提高60%。位運(yùn)算的容易應(yīng)用 有時(shí)我們的程序需要一個(gè)規(guī)模不大的hash表來記錄狀態(tài)。比如，做數(shù)獨(dú)時(shí)我們需要27個(gè)hash表來統(tǒng)計(jì)每一行、每一列和每一個(gè)小九宮格里已經(jīng)有哪些數(shù)了。此時(shí)，我們可以用27個(gè)小于29的整數(shù)舉行記錄。例如，一個(gè)只填了2和5的小九宮格就用數(shù)字18表示（二進(jìn)制為000010010），而某一行的狀態(tài)為511則表示這一行已經(jīng)填滿。需要轉(zhuǎn)變狀態(tài)時(shí)我們不需要把這個(gè)數(shù)轉(zhuǎn)成二進(jìn)制修改后再轉(zhuǎn)回去，而是

10、挺直舉行位操作。在搜尋時(shí)，把狀態(tài)表示成整數(shù)可以更好地舉行判重等操作。這道題是在搜尋中用法位運(yùn)算加速的經(jīng)典例子。以后我們會看到更多的例子。 下面列舉了一些頻繁的二進(jìn)制位的變換操作。 功能 | 示例 | 位運(yùn)算-+-+-去掉最后一位 | (101101- 10110) | x shr 1在最后加一個(gè)0 | (101101- 1011010) | x shl 1在最后加一個(gè)1 | (101101- 1011011) | x shl 1+1把最后一位變成1 | (101100- 101101) | x or 1把最后一位變成0 | (101101- 101100) | x or 1-1最后一位取反 |

11、 (101101- 101100) | x xor 1把右數(shù)第k位變成1 | (101001- 101101,k=3) | x or (1 shl (k-1)把右數(shù)第k位變成0 | (101101- 101001,k=3) | x and not (1 shl (k-1)右數(shù)第k位取反 | (101001- 101101,k=3) | x xor (1 shl (k-1)取末三位 | (1101101- 101) | x and 7取末k位 | (1101101- 1101,k=5) | x and (1 shl k-1)取右數(shù)第k位 | (1101101- 1,k=4) | x shr (k

12、-1) and 1把末k位變成1 | (101001- 101111,k=4) | x or (1 shl k-1)末k位取反 | (101001- 100110,k=4) | x xor (1 shl k-1)把右邊延續(xù)的1變成0 | (100101111- 100100000) | x and (x+1)把右起第一個(gè)0變成1 | (100101111- 100111111) | x or (x+1)把右邊延續(xù)的0變成1 | (11011000- 11011111) | x or (x-1)取右邊延續(xù)的1 | (100101111- 1111) | (x xor (x+1) shr 1去掉右起第一個(gè)1的左邊 | (100101000- 1000) | x and (x xor (x-1) 最后這一個(gè)在樹狀數(shù)組中會用到。pascal和c中的16進(jìn)制表示