位运算
各種位運(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，對這個(gè)數(shù)or 1之后再減一就可以了，其實(shí)際意義就是把這個(gè)數(shù)強(qiáng)行變成最接近的偶數(shù)。
=== 3. xor運(yùn)算 ===
xor運(yùn)算通常用于對二進(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)算可以用于簡單的加密。
定義兩個(gè)符號(hào)#和@ ，這兩個(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的對象是無符號(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( "%dn", a );
return 0;
}如果not的對象是有符號(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)榍罢呤歉讓右恍┑牟僮?。因此程序中乘?的操作請盡量用左移一位來代替。
定義一些常量可能會(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%。
1.技巧一：用于消去x的最后一位的1
x & (x-1)
x = 1100
x-1 = 1011
x & (x-1) = 10001.1.用O(1)時(shí)間檢測整數(shù)n是否是2的冪次.
思路解析：N如果是2的冪次，則N滿足兩個(gè)條件。
1.N>0
2.N的二進(jìn)制表示中只有一個(gè)1
一位N的二進(jìn)制表示中只有一個(gè)1，所以使用N&(N-1)將唯一的一個(gè)1消去。
如果N是2的冪次，那么N&(N-1)得到結(jié)果為0，即可判斷。
1.2.計(jì)算在一個(gè) 32 位的整數(shù)的二進(jìn)制表示中有多少個(gè) 1.
思路解析：
由 x & (x-1) 消去x最后一位知。循環(huán)使用x & (x-1)消去最后一位1，計(jì)算總共消去了多少次即可。
1.3.將整數(shù)A轉(zhuǎn)換為B，需要改變多少個(gè)bit位
思路解析
這個(gè)應(yīng)用是上面一個(gè)應(yīng)用的拓展。
思考將整數(shù)A轉(zhuǎn)換為B，如果A和B在第i（0<=i<32）個(gè)位上相等，則不需要改變這個(gè)BIT位，如果在第i位上不相等，則需要改變這個(gè)BIT位。所以問題轉(zhuǎn)化為了A和B有多少個(gè)BIT位不相同。聯(lián)想到位運(yùn)算有一個(gè)異或操作，相同為0，相異為1，所以問題轉(zhuǎn)變成了計(jì)算A異或B之后這個(gè)數(shù)中1的個(gè)數(shù)。
2.技巧二 使用二進(jìn)制進(jìn)行子集枚舉
應(yīng)用.給定一個(gè)含不同整數(shù)的集合，返回其所有的子集
樣例
如果 S = [1,2,3]，有如下的解：
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2] ]
思路
思路就是使用一個(gè)正整數(shù)二進(jìn)制表示的第i位是1還是0，代表集合的第i個(gè)數(shù)取或者不取。所以從0到2n-1總共2n個(gè)整數(shù)，正好對應(yīng)集合的2^n個(gè)子集。
S = {1,2,3}
N bit Combination
0 000 {}
1 001 {1}
2 010 {2}
3 011 {1,2}
4 100 {3}
5 101 {1,3}
6 110 {2,3}
7 111 {1,2,3}技巧三.a^b^b=a
3.1.應(yīng)用一 數(shù)組中，只有一個(gè)數(shù)出現(xiàn)一次，剩下都出現(xiàn)三次，找出出現(xiàn)一次的。
問題
Given [1,2,2,1,3,4,3], return 4
解題思路
因?yàn)橹挥幸粋€(gè)數(shù)恰好出現(xiàn)一個(gè)，剩下的都出現(xiàn)過兩次，所以只要將所有的數(shù)異或起來，就可以得到唯一的那個(gè)數(shù)。
#include<stdio.h>
int main()
{
int a[7]={1,2,2,1,3,4,3};
int ans=0;
for(int i=0;i<7;i++){
ans^=a[i];
}
printf("%d
",ans);
}
3.2.應(yīng)用二 數(shù)組中，只有一個(gè)數(shù)出現(xiàn)一次，剩下都出現(xiàn)三次，找出出現(xiàn)一次的。
問題
Given [1,1,2,3,3,3,2,2,4,1] return 4
解題思路
因?yàn)閿?shù)是出現(xiàn)三次的，也就是說，對于每一個(gè)二進(jìn)制位，如果只出現(xiàn)一次的數(shù)在該二進(jìn)制位為1，那么這個(gè)二進(jìn)制位在全部數(shù)字中出現(xiàn)次數(shù)無法被3整除。
模3運(yùn)算只有三種狀態(tài)：00,01,10，因此我們可以使用兩個(gè)位來表示當(dāng)前位%3，對于每一位，我們讓Two，One表示當(dāng)前位的狀態(tài)，B表示輸入數(shù)字的對應(yīng)位，Two+和One+表示輸出狀態(tài)。0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 1 0
1 0 1 0 0
One+ = (One ^ B) & (~Two)
Two+ = (~One+) & (Two ^ B)
#include<stdio.h>
void findNum(int *a,int n)
{
int one=0;
int two=0;
int i,j,k;
for(i=0;i<n;i++){
two=two|(one&a[i]);
one=one^a[i];
int three=two&one;
two=two^three;
one=one^three;
}
printf("%d
",one|two);
}
int main()
{
int a[10]={1,1,2,3,3,3,2,2,4,1};
findNum(a,10);
}另外一種容易理解的方法
#include<stdio.h>
void findNum(int *a,int n)
{
int ans=0;
int bits[32]={0};
for(int i=0;i<n;i++){
for(int j=0;j<32;j++){
bits[j]+=((a[i]>>j)&1);
}
}
for(int i=0;i<32;i++){
if(bits[i]%3==1) ans+=1<<i;
}
printf("%d
",ans);
}
int main()
{
int a[10]={1,1,2,3,3,3,2,2,4,1};
findNum(a,10);
}
3.3.應(yīng)用三 數(shù)組中，只有兩個(gè)數(shù)出現(xiàn)一次，剩下都出現(xiàn)兩次，找出出現(xiàn)一次的
問題
Given [1,2,2,3,4,4,5,3] return 1 and 5
解題思路
有了第一題的基本的思路，我們不妨假設(shè)出現(xiàn)一個(gè)的兩個(gè)元素是x，y，那么最終所有的元素異或的結(jié)果就是res = x^y。并且res！=0，那么我們可以找出res二進(jìn)制表示中的某一位是1，那么這一位1對于這兩個(gè)數(shù)x,y只有一個(gè)數(shù)的該位置是1。對于原來的數(shù)組，我們可以根據(jù)這個(gè)位置是不是1就可以將數(shù)組分成兩個(gè)部分。求出x,y其中一個(gè)，我們就能求出兩個(gè)了。
#include<stdio.h>
void findNum(int *a,int n)
{
int ans=0;
int pos=0;
int x=0,y=0;
for(int i=0;i<n;i++)
ans^=a[i];
int tmp=ans;
while((tmp&1)==0){
//終止條件是二進(jìn)制tmp最低位是1
pos++;
tmp>>=1;
}
for(int i=0;i<n;i++){
if((a[i]>>pos)&1){//取出第pos位的值
x^=a[i];
}
}
y=x^ans;
if(x>y) swap(x,y);//從大到小輸出x,y
printf("%d %d
",x,y);
}
int main()
{
int a[8]={1,2,2,3,4,4,5,3};
findNum(a,8);
}另外一種寫法
#include<stdio.h>
void findNum(int *a,int n)
{
int diff=0;
int x=0,y=0;
for(int i=0;i<n;i++){
diff^=a[i];
}
diff&=-diff;//取diff的最后一位1的位置
for(int i=0;i<n;i++){
if((a[i]&diff)==0){
x^=a[i];
}else y^=a[i];
}
if(x>y) swap(x,y);
printf("%d %d
",x,y);
}
int main()
{
int a[10]={1,2,2,3,4,4,5,3};
findNum(a,8);
}還沒看完的
位運(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ì)用到。
二進(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
XOR0000000000010100000011101101100
—————————————
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。對這個(gè)數(shù)進(jìn)行第二次異或的結(jié)果如下：
00000000000111100000100110110100
XOR 000000000001111000001001101101
—————————————
00000000000110011000101111011001
結(jié)果里的每個(gè)1表示原數(shù)的該位置及其前面三個(gè)位置中共有奇數(shù)個(gè)1，每個(gè)0就表示原數(shù)對應(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è)程序是如何對一個(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ù)位對齊。
二分查找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)算來取絕對值
這是一個(gè)非常有趣的問題。大家先自己想想吧，Ctrl+A顯示答案。
答案：假設(shè)x為32位整數(shù)，則x xor (not (x shr 31) + 1) + x shr 31的結(jié)果是x的絕對值
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 (nshl 16) );
end.
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è)對角線方向的限制條件下這一行的哪些地方不能放。我們以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è)對角線方向的禁位對下一行的影響需要平移一位。最后，如果遞歸到某個(gè)時(shí)候發(fā)現(xiàn)row=111111了，說明六個(gè)皇后全放進(jìn)去了，此時(shí)程序從第1行跳到第11行，找到的解的個(gè)數(shù)加一。
~~~~====~~~~===== 華麗的分割線 =====~~~~====~~~~
Gray碼
假如我有4個(gè)潛在的GF，我需要決定最終到底和誰在一起。一個(gè)簡單的辦法就是，依次和每個(gè)MM交往一段時(shí)間，最后選擇給我?guī)淼摹皾M意度”最大的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的遍歷順序照搬下來，然后把它們對稱翻折下去并在最前面加上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)步驟?，F(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ù)即是對原數(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.
總結(jié)
- 上一篇： 分享一个自用小功能--微信小程序二维码签
- 下一篇： 求军队文职闭坑机构？