位
運(yùn)算簡介及實(shí)用技巧（一）：基礎(chǔ)篇 FROM:Matrix67大牛
去年年底寫的關(guān)于
位運(yùn)算的日志是這個(gè)Blog里少數(shù)大受歡迎的文章之一，很多人都希望我能不斷完善那篇文章。后來我看到了不少其
它的資料，學(xué)習(xí)到了更多關(guān)于位運(yùn)算的知識(shí)，有了重新整理位運(yùn)算技巧的想法。從今天起我就開始寫這一系列位運(yùn)算講解文章，與其說是原來那篇文章的
follow-up，不如說是一個(gè)remake。當(dāng)然首先我還是從最基礎(chǔ)的東西說起。
什么是位運(yùn)算？
程序中的所有數(shù)在計(jì)
算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲(chǔ)存的。位運(yùn)算說穿了，就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作。比如，and運(yùn)算本來是一個(gè)邏輯運(yùn)算符，但整數(shù)與整數(shù)之
間也可以進(jìn)行and運(yùn)算。舉個(gè)例子，6的二進(jìn)制是110，11的二進(jìn)制是1011，那么6 and
11的結(jié)果就是2，它是二進(jìn)制對(duì)應(yīng)位進(jìn)行邏輯運(yùn)算的結(jié)果（0表示False，1表示True，空位都當(dāng)0處理）：
110
AND
1011
----------
0010 --> 2
由于位運(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作，不需要轉(zhuǎn)成
十進(jìn)制，因此處理速度非常快。當(dāng)然有人會(huì)說，這個(gè)快了有什么用，計(jì)算6 and
11沒有什么實(shí)際意義啊。這一系列的文章就將告訴你，位運(yùn)算到底可以干什么，有些什么經(jīng)典應(yīng)用，以及如何用位運(yùn)算優(yōu)化你的程序。
Pascal
和C中的位運(yùn)算符號(hào)
下面的a和b都是整數(shù)類型，則：
C語言 | Pascal語言
-------+-------------
a
& b | a and b
a | b | a or b
a ^ b | a xor b
~a
| not a
a << b | a shl b
a >> b | a shr b
注
意C中的邏輯運(yùn)算和位運(yùn)算符號(hào)是不同的。520|1314=1834，但520||1314=1，因?yàn)檫壿嬤\(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。如果需要把二進(jìn)制最末位變成0，對(duì)這個(gè)數(shù)or
1之后再減一就可以了，其實(shí)際意義就是把這個(gè)數(shù)強(qiáng)行變成最接近的偶數(shù)。
=== 3. xor運(yùn)算 ===
xor
運(yùn)算通常用于對(duì)二進(jìn)制的特定一位進(jìn)行取反操作，因?yàn)楫惢蚩梢赃@樣定義：0和1異或0都不變，異或1則取反。
xor運(yùn)算的逆運(yùn)算是它本身，
也就是說兩次異或同一個(gè)數(shù)最后結(jié)果不變，即(a xor b) xor b =
a。xor運(yùn)算可以用于簡單的加密，比如我想對(duì)我MM說1314520，但怕別人知道，于是雙方約定拿我的生日19880516作為密鑰。1314520
xor 19880516 = 20665500，我就把20665500告訴MM。MM再次計(jì)算20665500 xor
19880516的值，得到1314520，于是她就明白了我的企圖。
下面我們看另外一個(gè)東西。定義兩個(gè)符號(hào)#和@（我怎么找不到那個(gè)圈
里有個(gè)叉的字符），這兩個(gè)符號(hào)互為逆運(yùn)算，也就是說(x # y) @ y = x。現(xiàn)在依次執(zhí)行下面三條命令，結(jié)果是什么？
x
<- x # y
y <- x @ y
x <- x @ y 執(zhí)行了第一句后x變成了x
# y。那么第二句實(shí)質(zhì)就是y <- x # y @ y，由于#和@互為逆運(yùn)算，那么此時(shí)的y變成了原來的x。第三句中x實(shí)際上被賦值為(x #
y) @ x，如果#運(yùn)算具有交換律，那么賦值后x就變成最初的y了。這三句話的結(jié)果是，x和y的位置互換了。
加法和減法互為逆運(yùn)算，
并且加法滿足交換律。把#換成+，把@換成-，我們可以寫出一個(gè)不需要臨時(shí)變量的swap過程(Pascal)。
procedure
swap(var a,b:longint);
begin
a:=a + b;
b:=a - b;
a:=a - b;
end; 好了，剛才不是說xor的逆運(yùn)算是它本身嗎？于是我們就有了一個(gè)看起來非常詭異的
swap過程：
procedure 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í)要格外小心，你需要注意整數(shù)類型有沒有符號(hào)。
如果not的對(duì)象是無符號(hào)整數(shù)（不能表示負(fù)數(shù)），那么得到的值就是它與該類型上界的差，因?yàn)闊o符號(hào)類型的數(shù)是用$0000到$FFFF依次表示的。下面的
兩個(gè)程序（僅語言不同）均返回65435。
var
a:word;
begin
a:=100;
a:=not a;
writeln(a);
end.#include
<stdio.h>
int main()
{
unsigned short a=100;
a
= ~a;
printf( "%d\n", a );
return 0;
} 如
果not的對(duì)象是有符號(hào)的整數(shù)，情況就不一樣了，稍后我們會(huì)在“整數(shù)類型的儲(chǔ)存”小節(jié)中提到。
=== 5. shl運(yùn)算 ===
a
shl
b就表示把a(bǔ)轉(zhuǎn)為二進(jìn)制后左移b位（在后面添b個(gè)0）。例如100的二進(jìn)制為1100100，而110010000轉(zhuǎn)成十進(jìn)制是400，那么100
shl 2 = 400。可以看出，a shl b的值實(shí)際上就是a乘以2的b次方，因?yàn)樵诙M(jìn)制數(shù)后添一個(gè)0就相當(dāng)于該數(shù)乘以2。
通常
認(rèn)為a shl 1比a * 2更快，因?yàn)榍罢呤歉讓右恍┑牟僮鳌Ｒ虼顺绦蛑谐艘?的操作請(qǐng)盡量用左移一位來代替。
定義一些常量可能會(huì)
用到shl運(yùn)算。你可以方便地用1 shl 16 -
1來表示65535。很多算法和數(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次方（取整）。我們也經(jīng)常用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è)小于2^9的整數(shù)進(jìn)行記錄。例如，一個(gè)只填
了2和5的小九宮格就用數(shù)字18表示（二進(jìn)制為000010010），而某一行的狀態(tài)為511則表示這一行已經(jīng)填滿。需要改變狀態(tài)時(shí)我們不需要把這個(gè)數(shù)轉(zhuǎn)
成二進(jìn)制修改后再轉(zhuǎn)回去，而是直接進(jìn)行位操作。在搜索時(shí)，把狀態(tài)表示成整數(shù)可以更好地進(jìn)行判重等操作。
這道題是在搜索中使用位運(yùn)算加速的經(jīng)典例子。以后我們會(huì)看到更多的例子。
下面列舉了一些常見的
二進(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
最后一位取反 |
(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-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ù)組
中會(huì)用到。
Pascal和C中的16進(jìn)制表示
Pascal中需要在16進(jìn)制數(shù)前加$符號(hào)表示，C中需要在前面加
0x來表示。這個(gè)以后我們會(huì)經(jīng)常用到。
整數(shù)類型的儲(chǔ)存
我們前面所說的位運(yùn)算都沒有涉及負(fù)數(shù)，都假設(shè)這些運(yùn)算是在
unsigned/word類型（只能表示正數(shù)的整型）上進(jìn)行操作。但計(jì)算機(jī)如何處理有正負(fù)符號(hào)的整數(shù)類型呢？下面兩個(gè)程序都是考察16位整數(shù)的儲(chǔ)存方式
（只是語言不同）。
var
a,b:integer;
begin
a:=$0000;
b:=$0001;
write(a,' ',b,' ');
a:=$FFFE;
b:=$FFFF;
write(a,' ',b,' ');
a:=$7FFF;
b:=$8000;
writeln(a,'
',b);
end.#include <stdio.h>
int main()
{
short
int a, b;
a = 0×0000;
b = 0×0001;
printf( "%d %d
", a, b );
a = 0xFFFE;
b = 0xFFFF;
printf( "%d %d
", a, b );
a = 0×7FFF;
b = 0×8000;
printf( "%d
%d\n", a, b );
return 0;
} 兩個(gè)程序的輸出均為0 1 -2 -1
32767
-32768。其中前兩個(gè)數(shù)是內(nèi)存值最小的時(shí)候，中間兩個(gè)數(shù)則是內(nèi)存值最大的時(shí)候，最后輸出的兩個(gè)數(shù)是正數(shù)與負(fù)數(shù)的分界處。由此你可以清楚地看到計(jì)算機(jī)是
如何儲(chǔ)存一個(gè)整數(shù)的：計(jì)算機(jī)用$0000到$7FFF依次表示0到32767的數(shù)，剩下的$8000到$FFFF依次表示-32768到-1的數(shù)。32位
有符號(hào)整數(shù)的儲(chǔ)存方式也是類似的。稍加注意你會(huì)發(fā)現(xiàn)，二進(jìn)制的第一位是用來表示正負(fù)號(hào)的，0表示正，1表示負(fù)。這里有一個(gè)問題：0本來既不是正數(shù)，也不是
負(fù)數(shù)，但它占用了$0000的位置，因此有符號(hào)的整數(shù)類型范圍中正數(shù)個(gè)數(shù)比負(fù)數(shù)少一個(gè)。對(duì)一個(gè)有符號(hào)的數(shù)進(jìn)行not運(yùn)算后，最高位的變化將導(dǎo)致正負(fù)顛倒，
并且數(shù)的絕對(duì)值會(huì)差1。也就是說，not a實(shí)際上等于-a-1。這種整數(shù)儲(chǔ)存方式叫做“補(bǔ)碼”。
最后還有兩句話
Matrix67
原創(chuàng)
轉(zhuǎn)貼請(qǐng)注明出處
位
運(yùn)算簡介及實(shí)用技巧（二）：進(jìn)階篇(1)
===== 真正強(qiáng)的東西來了！ =====
二進(jìn)制中的1有奇數(shù)個(gè)還是偶數(shù)個(gè)
我們可以用下面的代碼來計(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)制
101000000111011011000中有9個(gè)1，則x=1314520時(shí)程序輸出1。
var
i,x,c:longint;
begin
readln(x);
c:=0;
for i:=1 to
32 do
begin
c:=c + x and 1;
x:=x shr 1;
end;
writeln( c and 1 );
end.
但這樣的效率并不高，位運(yùn)算的神奇之處還
沒有體現(xiàn)出來。
同樣是判斷二進(jìn)制中1的個(gè)數(shù)的奇偶性，下面這段代碼就強(qiáng)了。你能看出這個(gè)代碼的原理嗎？
var
x:longint;
begin
readln(x);
x:=x xor (x shr 1);
x:=x xor (x shr 2);
x:=x xor (x shr 4);
x:=x xor (x shr 8);
x:=x xor (x shr 16);
writeln(x and 1);
end.
為了說明
上面這段代碼的原理，我們還是拿1314520出來說事。1314520的二進(jìn)制為101000000111011011000，第一次異或操作的結(jié)果如
下：
00000000000101000000111011011000
XOR 0000000000010100000011101101100
---------------------------------------
00000000000111100000100110110100
得
到的結(jié)果是一個(gè)新的二進(jìn)制數(shù)，其中右起第i位上的數(shù)表示原數(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é)果如下：
00000000000111100000100110110100
XOR
000000000001111000001001101101
---------------------------------------
00000000000110011000101111011001
結(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)過下面五次賦值后，x的值就是原數(shù)的二進(jìn)制表示中數(shù)字1的個(gè)數(shù)。比如，初始時(shí)x為1314520（網(wǎng)友抓狂：能不能換一個(gè)數(shù)啊），那么最后
x就變成了9，它表示1314520的二進(jìn)制中有9個(gè)1。
x := (x and $55555555) + ((x shr 1)
and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and
$00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) +
((x shr 16) and $0000FFFF);
為了便于解說，我們下面僅說明這個(gè)程序是如何對(duì)一個(gè)8位整數(shù)進(jìn)
行處理的。我們拿數(shù)字211（我們班某MM的生日）來開刀。211的二進(jìn)制為11010011。
+---+---+---+---+---+---+---+---+
|
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原數(shù)
+---+---+---+---+---+---+---+---+
| 1
0 | 0 1 | 0 0 | 1 0 | <---第一次運(yùn)算后
+-------+-------+-------+-------+
| 0
0 1 1 | 0 0 1 0 | <---第二次運(yùn)算后
+---------------+---------------+
| 0
0 0 0 0 1 0 1 | <---第三次運(yùn)算后，得數(shù)為5
+-------------------------------+
整
個(gè)程序是一個(gè)分治的思想。第一次我們把每相鄰的兩位加起來，得到每兩位里1的個(gè)數(shù)，比如前兩位10就表示原數(shù)的前兩位有2個(gè)1。第二次我們繼續(xù)兩兩相
加，10+01=11，00+10=10，得到的結(jié)果是00110010，它表示原數(shù)前4位有3個(gè)1，末4位有2個(gè)1。最后一次我們把0011和0010
加起來，得到的就是整個(gè)二進(jìn)制中1的個(gè)數(shù)。程序中巧妙地使用取位和右移，比如第二行中$33333333的二進(jìn)制為00110011001100….，用
它和x做and運(yùn)算就相當(dāng)于以2為單位間隔取數(shù)。shr的作用就是讓加法運(yùn)算的相同數(shù)位對(duì)齊。
二分查找32位整數(shù)的前導(dǎo)0個(gè)數(shù)
這
里用的C語言，我直接Copy的Hacker's
Delight上的代碼。這段代碼寫成C要好看些，寫成Pascal的話會(huì)出現(xiàn)很多begin和end，搞得代碼很難看。程序思想是二分查找，應(yīng)該很簡
單，我就不細(xì)說了。
int nlz(unsigned x)
{
int n;
if (x
== 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n
+16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x
<< 8;}
if ((x >> 28) == 0) {n = n + 4; x = x <<
4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
只用位運(yùn)算來取
絕對(duì)值
這是一個(gè)非常有趣的問題。大家先自己想想吧，Ctrl+A顯示答案。
答案：假設(shè)x為32位整數(shù)，則x xor
(not (x shr 31) + 1) + x shr 31的結(jié)果是x的絕對(duì)值
x shr
31是二進(jìn)制的最高位，它用來表示x的符號(hào)。如果它為0（x為正），則not (x shr 31) +
1等于$00000000，異或任何數(shù)結(jié)果都不變；如果最高位為1（x為負(fù)），則not (x shr 31) +
1等于$FFFFFFFF，x異或它相當(dāng)于所有數(shù)位取反，異或完后再加一。
高低位交換
這個(gè)題實(shí)際上是我出的，做為學(xué)校內(nèi)部NOIp模擬賽的第一題。題目是這樣：
給出一個(gè)小于2^32的正整數(shù)。這個(gè)數(shù)可以用一個(gè)32位的二進(jìn)制數(shù)表示（不足32位用0補(bǔ)足）。我們稱這個(gè)二進(jìn)
制數(shù)的前16位為“高位”，后16位為“低位”。將它的高低位交換，我們可以得到一個(gè)新的數(shù)。試問這個(gè)新的數(shù)是多少（用十進(jìn)制表示）。
例如，
數(shù)1314520用二進(jìn)制表示為0000 0000 0001 0100 0000 1110 1101
1000（添加了11個(gè)前導(dǎo)0補(bǔ)足為32位），其中前16位為高位，即0000 0000 0001 0100；后16位為低位，即0000 1110
1101 1000。將它的高低位進(jìn)行交換，我們得到了一個(gè)新的二進(jìn)制數(shù)0000 1110 1101 1000 0000 0000 0001
0100。它即是十進(jìn)制的249036820。
當(dāng)時(shí)幾乎沒有人想到用一句位操作來代替冗長的程序。使用位運(yùn)算的話兩句話就完了。
var
n:dword;
begin
readln( n );
writeln( (n shr 16) or
(n shl 16) );
end.
而事實(shí)上，Pascal有一個(gè)系統(tǒng)函數(shù)swap直接就可以用。
二
進(jìn)制逆序
下面的程序讀入一個(gè)32位整數(shù)并輸出它的二進(jìn)制倒序后所表示的數(shù)。
輸入：
1314520 （二進(jìn)制為00000000000101000000111011011000）
輸出：
460335104 （二進(jìn)制為00011011011100000010100000000000）
var
x:dword;
begin
readln(x);
x := (x and $55555555) shl 1
or (x and $AAAAAAAA) shr 1;
x := (x and $33333333) shl 2 or (x
and $CCCCCCCC) shr 2;
x := (x and $0F0F0F0F) shl 4 or (x and
$F0F0F0F0) shr 4;
x := (x and $00FF00FF) shl 8 or (x and
$FF00FF00) shr 8;
x := (x and $0000FFFF) shl 16 or (x and
$FFFF0000) shr 16;
writeln(x);
end.
它的原理和剛才求二進(jìn)制中1
的個(gè)數(shù)那個(gè)例題是大致相同的。程序首先交換每相鄰兩位上的數(shù)，以后把互相交換過的數(shù)看成一個(gè)整體，繼續(xù)進(jìn)行以2位為單位、以4位為單位的左右對(duì)換操作。我
們?cè)俅斡?位整數(shù)211來演示程序執(zhí)行過程：
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0
| 1 | 0 | 0 | 1 | 1 | <---原數(shù)
+---+---+---+---+---+---+---+---+
| 1
1 | 1 0 | 0 0 | 1 1 | <---第一次運(yùn)算后
+-------+-------+-------+-------+
| 1
0 1 1 | 1 1 0 0 | <---第二次運(yùn)算后
+---------------+---------------+
| 1
1 0 0 1 0 1 1 | <---第三次運(yùn)算后
+-------------------------------+
Copyright
也很強(qiáng)
writeln('Matrix' , 42 XOR 105 , '原創(chuàng)，轉(zhuǎn)貼請(qǐng)注明出處');
位
運(yùn)算簡介及實(shí)用技巧（三）：進(jìn)階篇(2)
今天我們來看兩個(gè)稍微復(fù)雜一點(diǎn)的例子。
n皇后問題位運(yùn)算版
n皇后問題是啥我就不說了吧，學(xué)編程的肯定都見過。下面
的十多行代碼是n皇后問題的一個(gè)高效位運(yùn)算程序，看到過的人都夸它牛。初始時(shí)，upperlim:=(1 shl
n)-1。主程序調(diào)用test(0,0,0)后sum的值就是n皇后總的解數(shù)。拿這個(gè)去交USACO，0.3s，暴爽。
procedure
test(row,ld,rd:longint);
var
pos,p:longint;
begin
{
1} if row<>upperlim then
{ 2} begin
{ 3}
pos:=upperlim and not (row or ld or rd);
{ 4} while pos<>0
do
{ 5} begin
{ 6} p:=pos and -pos;
{
7} pos:=pos-p;
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr
1);
{ 9} end;
{10} end
{11} else inc(sum);
end;
乍
一看似乎完全摸不著頭腦，實(shí)際上整個(gè)程序是非常容易理解的。這里還是建議大家自己單步運(yùn)行一探究竟，實(shí)在沒研究出來再看下面的解說。
和
普通算法一樣，這是一個(gè)遞歸過程，程序一行一行地尋找可以放皇后的地方。過程帶三個(gè)參數(shù)，row、ld和rd，分別表示在縱列和兩個(gè)對(duì)角線方向的限制條件
下這一行的哪些地方不能放。我們以6×6的棋盤為例，看看程序是怎么工作的。假設(shè)現(xiàn)在已經(jīng)遞歸到第四層，前三層放的子已經(jīng)標(biāo)在左圖上了。紅色、藍(lán)色和綠色
的線分別表示三個(gè)方向上有沖突的位置，位于該行上的沖突位置就用row、ld和rd中的1來表示。把它們?nèi)齻€(gè)并起來，得到該行所有的禁位，取反后就得到所
有可以放的位置（用pos來表示）。前面說過-a相當(dāng)于not a + 1，這里的代碼第6行就相當(dāng)于pos and (not pos +
1)，其結(jié)果是取出最右邊的那個(gè)1。這樣，p就表示該行的某個(gè)可以放子的位置，把它從pos中移除并遞歸調(diào)用test過程。注意遞歸調(diào)用時(shí)三個(gè)參數(shù)的變
化，每個(gè)參數(shù)都加上了一個(gè)禁位，但兩個(gè)對(duì)角線方向的禁位對(duì)下一行的影響需要平移一位。最后，如果遞歸到某個(gè)時(shí)候發(fā)現(xiàn)row=111111了，說明六個(gè)皇后
全放進(jìn)去了，此時(shí)程序從第1行跳到第11行，找到的解的個(gè)數(shù)加一。
~~~~====~~~~===== 華麗的分割線
=====~~~~====~~~~
Gray碼
假如我有4個(gè)潛在的GF，我需要決定最終到底和誰在一起。一個(gè)簡單的辦法
就是，依次和每個(gè)MM交往一段時(shí)間，最后選擇給我?guī)淼?#8220;滿意度”最大的MM。但看了dd牛的理論后，
事情開始變得復(fù)雜了：我可以選擇和多個(gè)MM在一起。這樣，需要考核的狀態(tài)變成了2^4=16種（當(dāng)然包括0000這一狀態(tài)，因?yàn)槲矣锌赡苁遣ＡВ，F(xiàn)在的
問題就是，我應(yīng)該用什么順序來遍歷這16種狀態(tài)呢？
傳統(tǒng)的做法是，用二進(jìn)制數(shù)的順序來遍歷所有可能的組合。也就是說，我需要以
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)系是一件何等巨大的工程啊。因此，我希望知道，是否有一種方法可以使得，從沒有MM這一狀態(tài)出發(fā)，每次只改變我和一個(gè)MM的關(guān)系（追或者甩），15次操
作后恰好遍歷完所有可能的組合（最終狀態(tài)不一定是1111）。大家自己先試一試看行不行。
解決這個(gè)問題的方法很巧妙。我們來說明，假如我
們已經(jīng)知道了n=2時(shí)的合法遍歷順序，我們?nèi)绾蔚玫絥=3的遍歷順序。顯然，n=2的遍歷順序如下：
00
01
11
10
你
可能已經(jīng)想到了如何把上面的遍歷順序擴(kuò)展到n=3的情況。n=3時(shí)一共有8種狀態(tài)，其中前面4個(gè)把n=2的遍歷順序照搬下來，然后把它們對(duì)稱翻折下去并在
最前面加上1作為后面4個(gè)狀態(tài)：
000
001
011
010 ↑
--------
110 ↓
111
101
100
用
這種方法得到的遍歷順序顯然符合要求。首先，上面8個(gè)狀態(tài)恰好是n=3時(shí)的所有8種組合，因?yàn)樗鼈兪窃趎=2的全部四種組合的基礎(chǔ)上考慮選不選第3個(gè)元素
所得到的。然后我們看到，后面一半的狀態(tài)應(yīng)該和前面一半一樣滿足“相鄰狀態(tài)間僅一位不同”的限制，而“鏡面”處則是最前面那一位數(shù)不同。再次翻折三階遍歷
順序，我們就得到了剛才的問題的答案：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
這
種遍歷順序作為一種編碼方式存在，叫做Gray碼（寫個(gè)中文讓蜘蛛來抓：格雷碼）。它的應(yīng)用范圍很廣。比如，n階的Gray碼相當(dāng)于在n維立方體上的
Hamilton回路，因?yàn)檠刂⒎襟w上的邊走一步，n維坐標(biāo)中只會(huì)有一個(gè)值改變。再比如，Gray碼和Hanoi塔問題等價(jià)。Gray碼改變的是第幾個(gè)
數(shù)，Hanoi塔就該移動(dòng)哪個(gè)盤子。比如，3階的Gray碼每次改變的元素所在位置依次為1-2-1-3-1-2-1，這正好是3階Hanoi塔每次移動(dòng)
盤子編號(hào)。如果我們可以快速求出Gray碼的第n個(gè)數(shù)是多少，我們就可以輸出任意步數(shù)后Hanoi塔的移動(dòng)步驟。現(xiàn)在我告訴你，Gray碼的第n個(gè)數(shù)（從
0算起）是n xor (n shr 1)，你能想出來這是為什么嗎？先自己想想吧。
下面我們把二進(jìn)制數(shù)和Gray碼都寫在下
面，可以看到左邊的數(shù)異或自身右移的結(jié)果就等于右邊的數(shù)。
二進(jìn)制數(shù) Gray碼
000 000
001 001
010 011
011 010
100
110
101 111
110 101
111 100
從
二進(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碼的生成方法。這就說明了，Gray碼的第n個(gè)數(shù)確實(shí)是n xor (n
shr 1)。
今年四月份mashuo給
我看了這道題，是二維意義上的Gray碼。題目大意是說，把0到2^(n+m)-1的數(shù)寫成2^n *
2^m的矩陣，使得位置相鄰兩數(shù)的二進(jìn)制表示只有一位之差。答案其實(shí)很簡單，所有數(shù)都是由m位的Gray碼和n位Gray碼拼接而成，需要用左移操作和
or運(yùn)算完成。完整的代碼如下：
var
x,y,m,n,u:longint;
begin
readln(m,n);
for x:=0 to 1 shl m-1 do begin
u:=(x xor (x
shr 1)) shl n; //輸出數(shù)的左邊是一個(gè)m位的Gray碼
for y:=0 to 1 shl n-1 do
write(u or (y xor (y shr 1)),' '); //并上一個(gè)n位Gray碼
writeln;
end;
end.
Matrix67原創(chuàng)
轉(zhuǎn)貼請(qǐng)注明出處
位運(yùn)算簡介及實(shí)用技巧（四）：實(shí)戰(zhàn)篇 下面
分享的是我自己寫的三個(gè)代碼，里面有些題目也是我自己出的。這些代碼都是在我的Pascal時(shí)代寫的，恕不提供C語言了。代碼寫得并不好，我只是想告訴大
家位運(yùn)算在實(shí)戰(zhàn)中的應(yīng)用，包括了搜索和狀態(tài)壓縮DP方面的題目。其實(shí)大家可以在網(wǎng)上找到更多用位運(yùn)算優(yōu)化的題目，這里整理出一些自己寫的代碼，只是為了原
創(chuàng)系列文章的完整性。這一系列文章到這里就結(jié)束了，希望大家能有所收獲。
Matrix67原創(chuàng)，轉(zhuǎn)貼請(qǐng)注明出處。
Problem : 費(fèi)解的開關(guān)
題目來源
06
年NOIp模擬賽（一） by Matrix67 第四題
問題描述
你玩過“拉燈”游戲嗎？25盞燈排成一個(gè)5×5的方
形。每一個(gè)燈都有一個(gè)開關(guān)，游戲者可以改變它的狀態(tài)。每一步，游戲者可以改變某一個(gè)燈的狀態(tài)。游戲者改變一個(gè)燈的狀態(tài)會(huì)產(chǎn)生連鎖反應(yīng)：和這個(gè)燈上下左右相
鄰的燈也要相應(yīng)地改變其狀態(tài)。
我們用數(shù)字“1”表示一盞開著的燈，用數(shù)字“0”表示關(guān)著的燈。下面這種狀態(tài)
10111
01101
10111
10000
11011
在
改變了最左上角的燈的狀態(tài)后將變成：
01111
11101
10111
10000
11011
再
改變它正中間的燈后狀態(tài)將變成：
01111
11001
11001
10100
11011
給
定一些游戲的初始狀態(tài)，編寫程序判斷游戲者是否可能在6步以內(nèi)使所有的燈都變亮。
輸入格式
第一行有一個(gè)正整數(shù)n，代表數(shù)
據(jù)中共有n個(gè)待解決的游戲初始狀態(tài)。
以下若干行數(shù)據(jù)分為n組，每組數(shù)據(jù)有5行，每行5個(gè)字符。每組數(shù)據(jù)描述了一個(gè)游戲的初始狀態(tài)。各組數(shù)
據(jù)間用一個(gè)空行分隔。
對(duì)于30%的數(shù)據(jù)，n<=5；
對(duì)于100%的數(shù)據(jù)，n<=500。
輸
出格式
輸出數(shù)據(jù)一共有n行，每行有一個(gè)小于等于6的整數(shù)，它表示對(duì)于輸入數(shù)據(jù)中對(duì)應(yīng)的游戲狀態(tài)最少需要幾步才能使所有燈變亮。
對(duì)
于某一個(gè)游戲初始狀態(tài)，若6步以內(nèi)無法使所有燈變亮，請(qǐng)輸出“-1”。
樣例輸入
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
樣
例輸出
3
2
-1
程序代碼
const
BigPrime=3214567;
MaxStep=6;
type
pointer=^rec;
rec=record
v:longint;
step:integer;
next:pointer;
end;
var
total:longint;
hash:array[0..BigPrime-1]of pointer;
q:array[1..400000]of rec;
function
update(a:longint;p:integer):longint;
begin
a:=a xor (1 shl p);
if p mod 5<>0 then a:=a xor (1 shl (p-1));
if (p+1) mod
5<>0 then a:=a xor (1 shl (p+1));
if p<20 then a:=a xor
(1 shl (p+5));
if p>4 then a:=a xor (1 shl (p-5));
exit(a);
end;
function find(a:longint;step:integer):boolean;
var
now:pointer;
begin
now:=hash[a mod BigPrime];
while
now<>nil do
begin
if now^.v=a then exit(true);
now:=now^.next;
end;
new(now);
now^.v:=a;
now^.step:=step;
now^.next:=hash[a mod BigPrime];
hash[a mod BigPrime]:=now;
total:=total+1;
exit(false);
end;
procedure solve;
var
p:integer;
close:longint=0;
open:longint=1;
begin
find(1 shl 25-1,0);
q[1].v:=1 shl 25-1;
q[1].step:=0;
repeat
inc(close);
for p:=0 to 24 do
if
not find(update(q[close].v,p),q[close].step+1) and
(q[close].step+1<MaxStep) then
begin
open:=open+1;
q[open].v:=update(q[close].v,p);
q[open].step:=q[close].step+1;
end;
until close>=open;
end;
procedure
print(a:longint);
var
now:pointer;
begin
now:=hash[a
mod BigPrime];
while now<>nil do
begin
if
now^.v=a then
begin
writeln(now^.step);
exit;
end;
now:=now^.next;
end;
writeln(-1);
end;
procedure main;
var
ch:char;
i,j,n:integer;
t:longint;
begin
readln(n);
for i:=1
to n do
begin
t:=0;
for j:=1 to 25 do
begin
read(ch);
t:=t*2+ord(ch)-48;
if j mod 5=0 then
readln;
end;
print(t);
if i<n then readln;
end;
end;
begin
solve;
main;
end.
======================= 性
感的分割線 =======================
Problem : garden / 和MM逛花園
題目來源
07年Matrix67生日邀請(qǐng)賽 第
四題
問題描述
花園設(shè)計(jì)強(qiáng)調(diào)，簡單就是美。Matrix67常去的花園有著非常簡單的布局：花園的所有景點(diǎn)的位置都是“對(duì)
齊”了的，這些景點(diǎn)可以看作是平面坐標(biāo)上的格點(diǎn)。相鄰的景點(diǎn)之間有小路相連，這些小路全部平行于坐標(biāo)軸。景點(diǎn)和小路組成了一個(gè)“不完整的網(wǎng)格”。
一
個(gè)典型的花園布局如左圖所示。花園布局在6行4列的網(wǎng)格上，花園的16個(gè)景點(diǎn)的位置用紅色標(biāo)注在了圖中。黑色線條表示景點(diǎn)間的小路，其余灰色部分實(shí)際并不
存在。
Matrix67
的生日那天，他要帶著他的MM在花園里游玩。Matrix67不會(huì)帶MM兩次經(jīng)過同一個(gè)景點(diǎn)，因此每個(gè)景點(diǎn)最多被游覽一次。他和他的MM邊走邊聊，他們是
如此的投入以致于他們從不會(huì)“主動(dòng)地拐彎”。也就是說，除非前方已沒有景點(diǎn)或是前方的景點(diǎn)已經(jīng)訪問過，否則他們會(huì)一直往前走下去。當(dāng)前方景點(diǎn)不存在或已游
覽過時(shí)，Matrix67會(huì)帶MM另選一個(gè)方向繼續(xù)前進(jìn)。由于景點(diǎn)個(gè)數(shù)有限，訪問過的景點(diǎn)將越來越多，遲早會(huì)出現(xiàn)不能再走的情況（即四個(gè)方向上的相鄰景點(diǎn)
都訪問過了），此時(shí)他們將結(jié)束花園的游覽。Matrix67希望知道以這種方式游覽花園是否有可能遍歷所有的景點(diǎn)。Matrix67可以選擇從任意一個(gè)景
點(diǎn)開始游覽，以任意一個(gè)景點(diǎn)結(jié)束。
在上圖所示的花園布局中，一種可能的游覽方式如右圖所示。這種瀏覽方式從(1,2)出發(fā)，以(2,4)
結(jié)束，經(jīng)過每個(gè)景點(diǎn)恰好一次。
輸入格式
第一行輸入兩個(gè)用空格隔開的正整數(shù)m和n，表示花園被布局在m行n列的網(wǎng)格上。
以
下m行每行n個(gè)字符，字符“0”表示該位置沒有景點(diǎn)，字符“1”表示對(duì)應(yīng)位置有景點(diǎn)。這些數(shù)字之間沒有空格。
輸出格式
你
的程序需要尋找滿足“不主動(dòng)拐彎”性質(zhì)且遍歷所有景點(diǎn)的游覽路線。
如果沒有這樣的游覽路線，請(qǐng)輸出一行“Impossible”（不帶引
號(hào)，注意大小寫）。
如果存在游覽路線，請(qǐng)依次輸出你的方案中訪問的景點(diǎn)的坐標(biāo)，每行輸出一個(gè)。坐標(biāo)的表示格式為“(x,y)”，代表第x
行第y列。
如果有多種方案，你只需要輸出其中一種即可。評(píng)測系統(tǒng)可以判斷你的方案的正確性。
樣例輸入
6 4
1100
1001
1111
1100
1110
1110
樣
例輸出
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)
數(shù)
據(jù)規(guī)模
對(duì)于30%的數(shù)據(jù)，n,m<=5；
對(duì)于100%的數(shù)據(jù)，n,m<=10。
程序代碼：
program garden;
const
dir:array[1..4,1..2]of integer=
((1,0),(0,1),(-1,0),(0,-1));
type
arr=array[1..10]of integer;
rec=record x,y:integer;end;
var
map:array[0..11,0..11]of boolean;
ans:array[1..100]of rec;
n,m,max:integer;
step:integer=1;
state:arr;
procedure
readp;
var
i,j:integer;
ch:char;
begin
readln(m,n);
for i:=1 to n do
begin
for j:=1 to m
do
begin
read(ch);
map[i,j]:=(ch='1');
inc(max,ord( map[i,j] ))
end;
readln;
end;
end;
procedure
writep;
var
i:integer;
begin
for i:=1 to step do
writeln(
'(' , ans[i].x , ',' , ans[i].y , ')' );
end;
procedure
solve(x,y:integer);
var
tx,ty,d:integer;
step_cache:integer;
state_cache:arr;
begin
step_cache:=step;
state_cache:=state;
if step=max then
begin
writep;
exit;
end;
for d:=1 to 4
do
begin
tx:=x+dir[d,1];
ty:=y+dir[d,2];
while
map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
begin
inc(step);
ans[step].x:=tx;
ans[step].y:=ty;
state[tx]:=state[tx] or ( 1 shl (ty-1) );
tx:=tx+dir[d,1];
ty:=ty+dir[d,2];
end;
tx:=tx-dir[d,1];
ty:=ty-dir[d,2];
if
(tx<>x) or (ty<>y) then solve(tx,ty);
state:=state_cache;
step:=step_cache;
end;
end;
{====main====}
var
i,j:integer;
begin
assign(input,'garden.in');
reset(input);
assign(output,'garden.out');
rewrite(output);
readp;
for i:=1 to n do
for j:=1 to m do
if map[i,j] then
begin
ans[1].x:=i;
ans[1].y:=j;
state[i]:=1
shl (j-1);
solve(i,j);
state[i]:=0;
end;
close(input);
close(output);
end.
======================= 性
感的分割線 =======================
Problem : cowfood / 玉米地
題目來源
USACO月賽
問
題描述
農(nóng)夫約翰購買了一處肥沃的矩形牧場，分成M*N(1<=M<=12;
1<=N<=12)個(gè)格子。他想在那里的一些格子中種植美味的玉米。遺憾的是，有些格子區(qū)域的土地是貧瘠的，不能耕種。
精明
的約翰知道奶牛們進(jìn)食時(shí)不喜歡和別的牛相鄰，所以一旦在一個(gè)格子中種植玉米，那么他就不會(huì)在相鄰的格子中種植，即沒有兩個(gè)被選中的格子擁有公共邊。他還沒
有最終確定哪些格子要選擇種植玉米。
作為一個(gè)思想開明的人，農(nóng)夫約翰希望考慮所有可行的選擇格子種植方案。由于太開明，他還考慮一個(gè)格子
都不選擇的種植方案！請(qǐng)幫助農(nóng)夫約翰確定種植方案總數(shù)。
輸入格式:
第一行：兩個(gè)用空格分隔的整數(shù)M和N
第
二行到第M+1行：第i+1行描述牧場第i行每個(gè)格子的情況，N個(gè)用空格分隔的整數(shù)，表示這個(gè)格子是否可以種植（1表示肥沃的、適合種植，0表示貧瘠的、
不可種植）
輸出格式
一個(gè)整數(shù)，農(nóng)夫約翰可選擇的方案總數(shù)除以 100,000,000 的余數(shù)
樣例輸入
2
3
1 1 1
0 1 0
樣例輸出
9
樣例說明
給可以種植玉米的格子編
號(hào)：
1 2 3
4
只
種一個(gè)格子的方案有四種(1,2,3或4)，種植兩個(gè)格子的方案有三種(13,14或34)，種植三個(gè)格子的方案有一種(134)，還有一種什么格子都不
種。
4+3+1+1=9。
數(shù)據(jù)規(guī)模
對(duì)于30%的數(shù)據(jù)，N,M<=4；
對(duì)于
100%的數(shù)據(jù)，N,M<=12。
程序代碼：
program cowfood;
const
d=100000000;
MaxN=12;
var
f:array[0..MaxN,1..2000]of
longint;
w:array[1..2000,1..2000]of boolean;
st:array[0..2000]of integer;
map:array[0..MaxN]of integer;
m,n:integer;
function Impossible(a:integer):boolean;
var
i:integer;
flag:boolean=false;
begin
for i:=1 to MaxN do
begin
if flag and (a and 1=1) then exit(true);
flag:=(a
and 1=1);
a:=a shr 1;
end;
exit(false);
end;
function
Conflict(a,b:integer):boolean;
var
i:integer;
begin
for i:=1 to MaxN do
begin
if (a and 1=1) and (b and 1=1)
then exit(true);
a:=a shr 1;
b:=b shr 1;
end;
exit(false);
end;
function CanPlace(a,b:integer):boolean;
begin
exit(a or b=b);
end;
procedure FindSt;
var
i:integer;
begin
for i:=0 to 1 shl MaxN-1 do
if not
Impossible(i) then
begin
inc(st[0]);
st[st[0]]:=i;
end;
end;
procedure Init;
var
i,j:integer;
begin
for i:=1 to st[0] do
for j:=i to
st[0] do
if not Conflict(st[i],st[j]) then
begin
w[i,j]:=true;
w[j,i]:=true;
end;
end;
procedure
Readp;
var
i,j,t,v:integer;
begin
readln(m,n);
for i:=1 to m do
begin
v:=0;
for j:=1 to n do
begin
read(t);
v:=v*2+t;
end;
map[i]:=v;
readln;
end;
end;
procedure Solve;
var
i,j,k:integer;
begin
f[0,1]:=1;
map[0]:=1 shl n-1;
for i:=1 to m do
for
j:=1 to st[0] do
if not CanPlace(st[j],map[i]) then f[i,j]:=-1
else
for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k]
then
f[i,j]:=(f[i,j]+f[i-1,k]) mod d;
end;
procedure
Writep;
var
j:integer;
ans:longint=0;
begin
for
j:=1 to st[0] do
if f[m,j]<>-1 then ans:=(ans+f[m,j])
mod d;
writeln(ans);
end;
begin
assign(input,'cowfood.in');
reset(input);
assign(output,'cowfood.out');
rewrite(output);
FindSt;
Init;
Readp;
Solve;
Writep;
close(input);
close(output);
end.