位運(yùn)算簡(jiǎn)介及實(shí)用技巧進(jìn)階篇

1、位運(yùn)算簡(jiǎn)介及實(shí)用技巧 進(jìn)階篇二進(jìn)制中的 1 有奇數(shù)個(gè)還是偶數(shù)個(gè)可以用下面的代碼來(lái)計(jì)算一個(gè) 32 位整數(shù)的二進(jìn)制中 1 的個(gè)數(shù)的奇偶性，當(dāng)輸入數(shù)據(jù)的二進(jìn)制表示里有偶數(shù)個(gè)數(shù)字 1 時(shí)程序輸出 0，有奇數(shù)個(gè)則輸出 1。例如，1314520 的二進(jìn)制程序代碼vari,x,c:long beginreadln(x); c:=0;for i:=1 to beginc:=c + x x:=x shrend;000 中有 9 個(gè) 1，則 x=1314520 時(shí)程序輸出 1。;32 doand 1;1;wriend.n( c and 1 );但這樣的效率并不運(yùn)算的神奇之處還沒(méi)有體現(xiàn)出來(lái)。同樣是判斷二進(jìn)制中 1

2、的個(gè)數(shù)的奇偶性，下面這段代碼就強(qiáng)了。你能看出這個(gè)代碼的原理嗎？程序代碼varx:longbegin;readln(x);x:=x x:=x x:=x x:=x x:=x wriend.xor xor xor xorxor(x(x(x(x(xshr shr shr shrshr1);2);4);8);16);n(x and 1);為了說(shuō)明上面這段代碼的原理，還是拿 1314520 出來(lái)說(shuō)事。1314520 的二進(jìn)制為000，第一次異或操作的結(jié)果如下：00000000000XOR 000000000000000000000000000100得到的結(jié)果是一個(gè)新的二進(jìn)制數(shù)，其中右起第 i 位上的數(shù)表示

3、原數(shù)中第 i 和 i+1 位上有奇數(shù)個(gè) 1 還是偶數(shù)個(gè) 1。比如，最右邊那個(gè) 0 表示原數(shù)末兩位有偶數(shù)個(gè) 1，右起第 3 位上的1 就表示原數(shù)的這個(gè)位置和前一個(gè)位置中有奇數(shù)個(gè) 1。對(duì)這個(gè)數(shù)進(jìn)行第二次異或的結(jié)果如下00000000000XOR00000000000100100000000000001結(jié)果里的每個(gè) 1 表示原數(shù)的該位置及其前面三個(gè)位置有奇數(shù)個(gè) 1，每個(gè) 0 就表示原數(shù)對(duì)應(yīng)的四個(gè)位置上共偶數(shù)個(gè) 1。一直做到第五次異或結(jié)束后，得到的二進(jìn)制數(shù)的最末位就表示整個(gè) 32 位數(shù)里有多少個(gè) 1，這就是最終想要的。計(jì)算二進(jìn)制中的 1 的個(gè)數(shù)同樣假設(shè) x 是一個(gè) 32 位整數(shù)。經(jīng)過(guò)下面五次賦值后，x

4、 的值就是原數(shù)的二進(jìn)制表示中數(shù)字 1 的個(gè)數(shù)。比如，初始時(shí) x 為 1314520（網(wǎng)友抓狂：能不能換一個(gè)數(shù)?。敲醋詈?x就變成了 9，它表示 1314520 的二進(jìn)制中有 9 個(gè) 1。程序代碼x x x xx:=:=:=:=:=(x(x(x(x(xand and and andand$55555555)$33333333)$0F0F0F0F)$00FF00FF)$0000F)+(x(x(x(x(xshr shr shr shrshr1)2)4)8)and and andand$55555555);$33333333);$0F0F0F0F);$00FF00FF);16) and $0000

5、F);為了便于解說(shuō)，下面僅說(shuō)明這個(gè)程序是如何對(duì)一個(gè) 8 位整數(shù)進(jìn)行處理的。拿數(shù)字 211（班某 MM 的生日）來(lái)開(kāi)刀。211 的二進(jìn)制為 11010011。+-+-+-+-+-+-+-+-+| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |+-+-+-+-+-+-+-+-+-原數(shù)|+|+|+10|01|00|10|-第一次運(yùn)算后+0011|0010|-第二次運(yùn)算后+0000 0101|16)24)28)30)=0)0)0)0)nnnn=n n nn+16;x x xx=x x xx16;+8;4;2;return n;31);只用位運(yùn)算來(lái)取絕對(duì)值這是一個(gè)非常有趣。大家先自己想想

6、吧，Ctrl+A 顯示。：假設(shè) x 為 32 位整數(shù)，則 x xor (not (x shr 31) + 1) + x shr31 的結(jié)果是 x的絕對(duì)值xhr 1 是二進(jìn)制的最，它用來(lái)表示 x 的符號(hào)。如果它為 0（x 為正），則 not x hr31)31) +等于$00000000，異或任何數(shù)結(jié)果都不變；如果最為 1（x 為負(fù)），則 not x hr1 等于$FF，x 異或它相當(dāng)于所有數(shù)位取反，異或完后再加一。高低位交換這個(gè)題實(shí)際上是我出的，做為學(xué)校內(nèi)容NOIp 模擬賽的第一題。題目是這樣：給出一個(gè)小于 232 的正整數(shù)。這個(gè)數(shù)可以用一個(gè) 32 位的二進(jìn)制數(shù)表示（32 位用0 補(bǔ)足）。稱這

7、個(gè)二進(jìn)制數(shù)的前 16 位為“”，后 16 位為“低位”。將它的高低位交換，可以得到一個(gè)新的數(shù)。試問(wèn)這個(gè)新的數(shù)是多少（用十進(jìn)制表示）。例如，數(shù)用二進(jìn)制表示為0000 0001 0100 0000 1110 1101 1000（添加了 11 個(gè)前導(dǎo) 0 補(bǔ)足為 32 位），其中前 16 位為，即 0000 0000 0001 0100；后 16 位為低位，即 0000 110 101 000。將它的高低位進(jìn)行交換，得到了一個(gè)新的二進(jìn)制數(shù) 00001110 1101 1000 0000 0000 0001 0100。它即是十進(jìn)制的 249036820。當(dāng)時(shí)幾乎沒(méi)有人想到用一句位操作來(lái)代替冗長(zhǎng)的程序。

8、使用位運(yùn)算的話兩句話就完了程序代碼varn:dword; beginreadln( n );wriend.n( (n shr 16) or (n shl 16) );而事實(shí)上，Pascal 有一個(gè)系統(tǒng)函數(shù) swap 直接就可以用。二進(jìn)制逆序下面的程序讀入一個(gè) 32 位整數(shù)并輸出它的二進(jìn)制倒序后所表示的數(shù)。輸入： 1314520（二進(jìn)制為 00000000000輸出： 460335104 （二進(jìn)制為 000程序代碼varx:dword; beginreadln(x);000）00000000000）x x x xx:=:=:=:=:=(x(x(x(x(xand and and andand$55

9、555555)$33333333)$0F0F0F0F)$00FF00FF)shl shl shl shlshl124816or (x or (x or (x or (xor (xand $AAAAAAAA) and $CCCCCCCC) and $F0F0F0F0)and $FF00FF00)shr shr shrshr1;2;4;8;$0000F)and $F0000)shr 16;wriend.n(x);它的原理和剛才求二進(jìn)制中 1 的個(gè)數(shù)那個(gè)例題是大致相同的。程序首先交換每相鄰兩位上的數(shù)，以后把互相交換過(guò)的數(shù)看成一個(gè)整體，繼續(xù)進(jìn)行以 2 位為、以 4 位為的左右對(duì)換操作。再次用 8 位整

10、數(shù) 211 來(lái)演示程序執(zhí)行過(guò)程：+-+-+-+-+-+-+-+-+| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |+-+-+-+-+-+-+-+-+-原數(shù)|+|+|+11|10|00|11|-第一次運(yùn)算后+1011|1100|-第二次運(yùn)算后+1100 1011|-第三次運(yùn)算后+n 皇后問(wèn)題位運(yùn)算版n 皇后問(wèn)題是啥我就不說(shuō)了吧，學(xué)編程的肯定都見(jiàn)過(guò)。下面的十多行代碼是 n 皇后問(wèn)題的一個(gè)高效位運(yùn)算程序，看到過(guò)的人都夸它牛。初始時(shí)，upperlim:=(1 shl n)-1。主程序調(diào)用 test(0,0,0)后 sum 的值就是 n 皇后總的解數(shù)。拿這個(gè)去交 USACO，0.3s，

11、暴爽。程序代碼procedure test(row,ld,rd:long); var,p:long;begin123456789if rowupperlim then begin:=upperlim and not (row or ld or rd);while beginp:=:=0 doand -p;test(row+p,(ld+p)shl 1,(rd+p)shr 1);end;1011endelse inc(sum);end;乍一看似乎完全摸不著頭腦，實(shí)際上整個(gè)程序是非常容易理解的。這里還是建議大家自己?jiǎn)尾竭\(yùn)行一探究竟，實(shí)在沒(méi)研究出來(lái)再看下面的解說(shuō)。和普通算法一樣，這是一個(gè)遞歸過(guò)程，程序

12、一行一行地尋找可以放皇后的地方。過(guò)程帶三個(gè)參數(shù)，row、ld 和 rd，分別表示在縱列和兩個(gè)對(duì)角線方向的限制條件下這一行的哪些地方不能放。以 6x6 的棋盤(pán)為例，看看程序是怎么工作的。假設(shè)現(xiàn)在已經(jīng)遞歸到第四層，前三層放的子已經(jīng)標(biāo)在左圖上了。紅色、藍(lán)色和綠色的線分別表示三個(gè)方向上有的位置，位于該行上的位置就用 row、ld 和 rd 中的 1 來(lái)表示。把它們?nèi)齻€(gè)并起來(lái)，得到該行所有的禁位，取反后就得到所有可以放的位置（用來(lái)表示）。前面-a 相當(dāng)于 not，這里的代碼第 6 行就相當(dāng)于and (not+ 1)，其結(jié)果是取出最右邊的那個(gè) 1。這樣，p 就表示該行的某個(gè)可以放子的位置，把它從中移除并遞

13、歸調(diào)用 test 過(guò)程。注意遞歸調(diào)用時(shí)三個(gè)參數(shù)的變化，每個(gè)參數(shù)都加上了一個(gè)禁位，但兩個(gè)對(duì)角線方向的禁位對(duì)下一行的影響需要平移一位。最后，如果遞歸到某個(gè)時(shí)候發(fā)現(xiàn) row=111111 了，說(shuō)明六個(gè)皇后全放進(jìn)去了，此時(shí)程序從第 1 行跳到第 11 行，找到的解的個(gè)數(shù)加一。=華麗的分割線=Gray 碼假如我有 4 個(gè)潛在的 GF，我需要決定最終到底和誰(shuí)在一起。一個(gè)簡(jiǎn)單的辦法就是，依次和每個(gè) MM 交往一段時(shí)間，最后選擇給我?guī)?lái)的“滿意度”最大的 MM。但看了 dd 牛的理論后，事情開(kāi)始變得復(fù)雜了：我可以選擇和多個(gè) MM 在一起。這樣，需要考核的狀態(tài)變成了24=16 種（當(dāng)然包括 0000 這一狀態(tài)，

14、因?yàn)槲矣锌赡苁遣ＡВ，F(xiàn)在什么順序來(lái)遍歷這 16 種狀態(tài)呢？就是，我應(yīng)該用傳統(tǒng)的做法是，用二進(jìn)制數(shù)的順序來(lái)遍歷所有可能的組合。也就是說(shuō)，我需要以0000-0001-0010-0011-0100-.-1111 這樣的順序?qū)γ糠N狀態(tài)進(jìn)試。這個(gè)順序很不科學(xué)，很多時(shí)候狀態(tài)的轉(zhuǎn)移都很耗時(shí)。比如從 0111 到 1000 時(shí)我需要暫時(shí)甩掉當(dāng)前所有的3 個(gè) MM，然后去把第 4 個(gè) MM。同時(shí)改變所有 MM 與關(guān)系是一件何等巨大的工程啊。因此，我希望知道，是否有法可以使得，從沒(méi)有 MM 這一狀態(tài)出發(fā)，每次只改變我和一個(gè) MM的關(guān)系（追或者甩），15 次操作后恰好遍歷完所有可能的組合（最終狀態(tài)不一定是 111

15、1）。大家自己先試一試看行。解決這個(gè)問(wèn)題的方法很巧妙來(lái)說(shuō)明，假如已經(jīng)知道了 n=2 時(shí)的合法遍歷順序，如何得到 n=3 的遍歷順序。顯然，n=2 的遍歷順序如下：00011110你可能已經(jīng)想到了如何把上面的遍歷順序擴(kuò)展到 n=3 的情況。n=3 時(shí)一共有 8 種狀態(tài)，其中前面 4 個(gè)把 n=2 的遍歷順序照搬下來(lái)，然后把它們對(duì)稱翻折下去并在最前面加上 1 作為后面 4 個(gè)狀態(tài)：000001011010 110 111101100用這種方法得到的遍歷順序顯然符合要求。首先，上面 8 個(gè)狀態(tài)恰好是 n=3 時(shí)的所有 8種組合，因?yàn)樗鼈兪窃?n=2 的全部四種組合的基礎(chǔ)上考慮選不選第 3 個(gè)元素所得

16、到的。然后看到，后面一半的狀態(tài)應(yīng)該和前面一半一樣滿足“相鄰狀態(tài)間僅一位不同”的限制，而“鏡面”處則是最前面那一位數(shù)不同。再次翻折三階遍歷順序，：就得到了剛才的0000000100110010011001110101010011001101111111101010101110011000這種遍歷順序作為一種編碼方式存在，叫做 Gray 碼（寫(xiě)個(gè)中文讓蜘蛛來(lái)抓：碼）。它的應(yīng)用范圍很廣。比如，n 階的 Gray 碼相當(dāng)于在 n 維立方體上的 Hamilton 回路，因?yàn)檠刂⒎襟w上的邊走一步，n 維坐標(biāo)中只會(huì)有一個(gè)值改變。再比如，Gray 碼和 Hanoi 塔問(wèn)題等價(jià)。Gray 碼改變的是第幾個(gè)數(shù)，

17、Hanoi 塔就該移動(dòng)哪個(gè)盤(pán)子。比如，3 階的 Gray 碼每次改變的元素所在位置依次為 1-2-1-3-1-2-1，這正好是 3 階 Hanoi 塔每次移動(dòng)盤(pán)子。如果可以快速求出 Gray 碼的第 n 個(gè)數(shù)是多少，就可以輸出任意步數(shù)后 Hanoi 塔的移動(dòng)步驟?，F(xiàn)在我告訴你，Gray 碼的第 n 個(gè)數(shù)（從 0 算起）是 n xor (n shr 1)，你能想出來(lái)這是為什么嗎？先自己想想吧。下面把二進(jìn)制數(shù)和 Gray 碼都寫(xiě)在下面，可以看到左邊的數(shù)異或自身右移的結(jié)果就等于右邊的數(shù)。二進(jìn)制數(shù)000001010011100101110111Gray 碼000001011010110111101100從二進(jìn)制數(shù)的角度看，“鏡像”位置上的數(shù)即是對(duì)原數(shù)進(jìn)行 not 運(yùn)算后的結(jié)果。比如，第 3 個(gè)數(shù) 010 和倒數(shù)第 3 個(gè)數(shù) 101 的每一位都正好相反。假設(shè)這兩個(gè)數(shù)分別為 x 和 y，那么 x xor (x shr 1)和 y xor (y shr 1)的結(jié)果只有一點(diǎn)不同：后者的首位是 1，前者的首位是0。而這正好是 Gray 碼的生成方法。這就說(shuō)明了，Gray 碼的第 n 個(gè)數(shù)確實(shí)是n or n hr )今年四月份 mashuo 給我看了這道題，是二維意義上的 Gray 碼。題目大意是說(shuō)，把 0到 2(n+m)-1 的數(shù)寫(xiě)成 2n * 2m 的矩陣，使得位置