The Fourth Dimension Space

=====   真正強(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)算后
+-------------------------------+

今天我們來看兩個(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ì)角線方向的限制條件下這一行的哪些地方不能放。我們以6x6的棋盤為例，看看程序是怎么工作的。假設(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)行測(cè)試。這個(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.