快速小測試：如何重寫(xiě)下面的語(yǔ)句？要求不使用條件判斷語(yǔ)句交換兩個(gè)常量的值。
if (x == a) x= b;
else x= a;
答案：x= a ^ b ^ x;
//此處變量x等于a或者等于b
字符^是邏輯異或XOR運算符。上面代碼為什么能工作呢？使用XOR運算符，一個(gè)變量執行2次異或運算與另一個(gè)變量，總是返回變量自身。
雖然Java位操作的魔術(shù)不是很普及，但是深入研究此技術(shù)有助于改善程序性能。在作者的機器配置下進(jìn)行基準測試，重寫(xiě)版本需5.2秒，使用邏輯判斷的版本需5.6秒。(測試代碼參見(jiàn)資源部分)。減少使用判斷語(yǔ)句通?？梢蕴岣咴诂F代多管道處理器上的程序性能。
對于Java程序員來(lái)說(shuō)，特別有益的是一些用來(lái)處理所謂bitsets位集的技巧。 Java語(yǔ)言中的原始類(lèi)型int和long也可被視為32位或64位的位集合?？梢越M合這些簡(jiǎn)單的結構來(lái)表示大型數據結構，比如數組。另外，還有一些特定的運算(bit-parallel 并行位運算),可以有效的將多個(gè)不同的運算壓縮為一個(gè)運算。使用以bit為單位的細粒度數據,而不是以integer整數為運算單位，我們會(huì )發(fā)現——對于integer整數來(lái)說(shuō)有時(shí)進(jìn)行的僅僅一步運算，如果使用bit位作為運算單位實(shí)際上可能進(jìn)行了許多操作?？梢哉J為Java語(yǔ)言中的位并行運算是軟件多通路技術(shù)的一種應用。
高級對弈程序如Crafty(使用C語(yǔ)言編寫(xiě))使用了特殊的數據結構——bitboard位圖棋盤(pán)來(lái)表示棋子的位置，這樣比使用數組的速度快很多。與C程序員相比，Java程序員更不應該使用數組。與C語(yǔ)言中數組的高效實(shí)現相比，Java語(yǔ)言中的數組實(shí)現(雖然提供了邊界檢查以及GC機制等額外功能)效率低下。為比較使用整數方案以及使用數組方案的性能，在作者機器(Windows XP, AMD Athlon, 熱部署Java虛擬機？)上進(jìn)行的簡(jiǎn)單測試顯示使用數組方案的運行時(shí)間是使用整數方案的160%，并且此處未考慮無(wú)用單元回收(garbage collection)對性能的影響。在某些情況下，可以使用整數位集替代數組。
下面會(huì )探討一下從匯編語(yǔ)言時(shí)代就存在的古董技巧，同時(shí)特別關(guān)注這些技巧在位集上的應用。Java作為可移植語(yǔ)言本身對位運算提供了良好的支持。進(jìn)一步，Java Tiger版本的API中又添加了一些用于位處理的方法。
典型Java環(huán)境下的位優(yōu)化Java程序運行在機器和操作系統之上，但是與機器和操作系統中充斥的位運算不同，Java程序基本上不包含大量的位運算。雖然現代CPU提供了特殊的位操作指令，不過(guò)在Java語(yǔ)言中無(wú)法執行這些特殊指令。JVM僅提供了有符號移位、無(wú)符號移位、位異或(bitewise XOR)、位或(bitwise OR)、位并(bitwise AND)以及位否(bitwise NOT)等位運算。有意思的是，并不僅僅是Java沒(méi)有提供額外的位運算，很多匯編程序員編寫(xiě)操作CPU的程序時(shí)，也會(huì )發(fā)現缺少同樣的位運算指令。兩類(lèi)程序員在位運算上的境遇其實(shí)一樣。匯編程序員不得不通過(guò)軟件模擬來(lái)實(shí)現這些指令，同時(shí)盡可能的保證效率。 Tiger版本的Java中許多方法也是通過(guò)使用純java代碼來(lái)模擬實(shí)現這些指令的。
進(jìn)行性能微調操作的C程序員可能會(huì )審查實(shí)際產(chǎn)生的匯編代碼、參考目標CPU的優(yōu)化器手冊、統計代碼執行的指令周期數目等方式來(lái)改善程序性能。與之相對，在Java程序里進(jìn)行這樣的底層優(yōu)化的一個(gè)實(shí)際問(wèn)題是無(wú)法確定優(yōu)化的效果。Sun公司的Java虛擬機規范(JVM spec)未給出某特定操作執行的相對速度?？梢詫⒆约赫J為執行速度快的代碼一部分再一部分的在Java虛擬機中執行，結果只能令人震驚——速度沒(méi)有提高甚至優(yōu)化部分可能降低原來(lái)程序性能。 Java虛擬機可能會(huì )攪亂破壞你做出的優(yōu)化，也可能在內部對一般的代碼優(yōu)化。 在任何情況下，通過(guò)JVM實(shí)現優(yōu)化, 即使編譯過(guò)后的程序提供這樣的支持，相應得優(yōu)化也需要進(jìn)行基準測試。
標準的查看字節碼的工具是JDK中包含的javap命令。Eclipse的使用者也可以利用由Andrei Loskutov開(kāi)發(fā)的字節碼查看插件。 Sun的網(wǎng)站上提供了JVM設計和指令集合的參考書(shū)的在線(xiàn)版本。注意，每個(gè)Java虛擬機內包含兩種類(lèi)型的內存. 一種是棧(stack)，用來(lái)存儲局部原始類(lèi)型變量和表達式；另一種是堆(heap),用來(lái)存儲對象和數組。堆內存儲的對象會(huì )被無(wú)用單元回收機制處理，而棧具有固定大小的內存塊。雖然大多數程序僅僅使用了?？臻g的很小部分，JVM規范聲明用戶(hù)可以認為棧至少有64k大小。請注意JVM可以被認為是一個(gè)32位或者64位的機器，所以字節byte以及位數少的原始類(lèi)型的運算不大可能比整數int的運算更快。
2的補數Java語(yǔ)言中，所有的整數原始類(lèi)型都是有符號數字，使用2的補數形式表示。要操作這些原始類(lèi)型，我們需要理解一些相關(guān)理論。
2的補數分成兩種：非負補數和負補數。補數的最高位，也是符號位，在一般系統上在最左邊。非負補數的此位是0?？梢院?jiǎn)單的從左到右讀取這些普通的非負補數，將他們轉換到任意進(jìn)制的整數。如果符號位設置為1，此數就是負數，除去符號位的右邊位集合與符號位一起表示此負數。
有兩種方法來(lái)考察負的補數。 首先，可以從可能的最小負數數起直到-1，比如，8位字節，從最小的10000000(-128)開(kāi)始，然后是10000001(-127),一直到11111111(-1)。另外一種考慮負的補數的方式有些古怪，當存在符號位時(shí)，用前面都是1后面跟著(zhù)個(gè)0來(lái)代替前面都是0后面跟著(zhù)個(gè)1的方式。然而，你最后需要從結果中減去1。 比如11111111時(shí)符號位后面跟著(zhù)7個(gè)1，(視為10000000)表示負零(-0),然后添加(也可以認為是減去)1，得到-1，同樣11111110(視為10000001，加上1是10000010)是-2，11111101(視為10000010，是-2，然后減去1)是-3，以此類(lèi)推。
感覺(jué)上有些怪，我們可以混合位運算符號和數學(xué)運算符號來(lái)進(jìn)行多種操作。比如將x變換為-x，可以表示為對x按位求反，然后加1，即(~x)+1，具體運算過(guò)程見(jiàn)下表。
布爾標記和標準布爾位集如下的位標記模式(bit flag pattern)是很普通的技術(shù)常識，在圖形用戶(hù)界面GUI程序的公用API中得到了廣泛應用。呵呵，我們可能正在為資源有限設備如蜂窩電話(huà)或者PDA編寫(xiě)一個(gè)Java GUI程序。對GUI中每個(gè)構件如按鈕(button)和下拉列表(drop-down list)都擁有一些Boolean選擇項標記。使用位標記，可以將許多選擇項安排到一個(gè)變量中。
//The constants to use with our GUI widgets: GUI構件使用的選擇項常量
final int visible = 1 << 0; // 1 可見(jiàn)？
final int enabled = 1 << 1; // 2 使能？
final int focusable = 1 << 2; // 4 focus？
final int borderOn = 1 << 3; // 8 有邊界？
final int moveable = 1 << 4; // 16 可移動(dòng)？
final int editable = 1 << 5; // 32 可編輯？
final int borderStyleA = 1 << 6; // 64 有樣式A邊界？
final int borderStyleB = 1 << 7; //128有樣式B邊界？
final int borderStyleC = 1 << 8; //256有樣式C邊界？
final int borderStyleD = 1 << 9; //512有樣式D邊界？
//etc.
myButton.setOptions( 1+2+4 );
//set a single widget.
int myDefault= 1+2+4; //A list of options.
int myExtras = 32+128; //Another list.
myButtonA.setOptions( myDefault );
myButtonB.setOptions( myDefault | myExtras );
在程序中可以將許多Boolean選擇項的位標記組合成一個(gè)參數，在一次符值操作中全部傳遞，這基本上不需要什么時(shí)間。API可能會(huì )聲明，每個(gè)組件在某時(shí)僅能使用邊界樣式A、邊界樣式B、邊界樣式C、或者邊界樣式D中的一種，那么可以通過(guò)使用掩碼(mask)來(lái)獲取對應的4位，然后檢查這4位中至多有一個(gè)1。下面代碼中的小技巧稍后會(huì )解釋。
int illegalOptionCombo= //不合法的組合框選項
2+ 64+ 128+ 512; // 10 11000010
int borderOptionMask= //邊界選項掩碼
64+ 128+ 256+ 512; // 11 11000000
int temp= illegalOptionCombo & //獲取4個(gè)邊界選項的所有的1位
borderOptionMask // 10 11000000
int rightmostBit= //獲得temp的最右邊的1
temp & ( -temp ); // 00 01000000
如果變量temp與rightMostBit不相等，那么表明temp必然含有多個(gè)1位。因為如果rightMostBit為0那么temp也應該是0，否則temp僅有一個(gè)1位。
if (temp != rightmostBit)
throw new IllegalArgumentException();
上面的示例是個(gè)玩具程序?，F實(shí)中，AWT和Swing使用了位標記模式，但是使用方式的不連貫。java.awt.geom.AffineTransform類(lèi)中使用了很多，java.awt.Font 和java.awt.InputEvent也使用了。
通用的位運算以及JDK 1.5的方法為了更好的應用位運算，需要掌握所謂的標準技巧，也就是那些可以應用的位運算方法。J2SE 5.0 Tiger版本內增加了一些新的位運算API。如果你使用的是老版本，只要剪切粘貼那些方法實(shí)現到你的代碼中。最近由Henry S. Warren,Jr編寫(xiě)的書(shū)籍Hacker‘s Delight內包含了很多關(guān)于位運算算法的資料。
下表展示了一些運算，這些運算可以通過(guò)一行代碼或者通過(guò)一次調用API方法實(shí)現
欲了解上面API方法的運行時(shí)間，可以閱讀JDK中相應的源碼。一些方法可能更難以理解一些。所有方法都在Hacker‘s Delight一書(shū)中進(jìn)行了解釋。這些API方法基本上都是一行代碼或者很少幾行代碼實(shí)現的，比下面給出的的highestOneBit(int)方法代碼。
public static int highestOneBit(int i)
{
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
高級秘笈，同志們?。ㄆ灞P(pán)的位圖棋盤(pán)模式）下面部分，就像烈酒伏特加和變幻莫測的鏡子一樣，其中的位運算變得很復雜。
在冷戰發(fā)展到頂點(diǎn)的時(shí)期，國際象棋是計算機科學(xué)的一個(gè)研究熱點(diǎn)。原蘇聯(lián)和美國各自獨立的提出了新的象棋數據結構——位圖棋盤(pán)。美國團隊——Slate和Atkin，基于Chess 4.x軟件出版了《人類(lèi)和機器的國際象棋技能》一書(shū)，其中有一章討論了位圖棋盤(pán)算法，這可能是最早的關(guān)于位圖棋盤(pán)算法的印刷品。 原蘇聯(lián)團隊，包括Donskoy以及其他人員，開(kāi)發(fā)了使用位圖棋盤(pán)算法的程序Kaissa。這兩個(gè)軟件在世界范圍都具有勝利性的競爭力。
在討論位圖棋盤(pán)算法前，我們先來(lái)看看使用Java語(yǔ)言(或其他許多語(yǔ)言)表示棋盤(pán)的標準方法。
//棋盤(pán)上64個(gè)格子所有可能狀態(tài)的整數枚舉
final int EMPTY = 0;
final int WHITE_PAWN = 1;
final int WHITE_KNIGHT = 2;
final int WHITE_BISHOP = 3;
final int WHITE_ROOK = 4;
final int WHITE_QUEEN = 5;
final int WHITE_KING = 6;
final int BLACK_PAWN = 7;
final int BLACK_KNIGHT = 8;
final int BLACK_BISHOP = 9;
final int BLACK_ROOK = 10;
final int BLACK_QUEEN = 11;
final int BLACK_KING = 12;
//使用含有64個(gè)元素的整數數組表示64個(gè)格子
int[] board= new int[64];
使用數組方法很直觀(guān)，相反，位圖棋盤(pán)算法的數據結構是使用12個(gè)64位的位集表示，每個(gè)表示一種類(lèi)型的棋子(每方6種棋子，共12種)。 如下圖，視覺(jué)上看上去好像是一個(gè)堆在另一個(gè)的上面。
//為棋盤(pán)聲明12個(gè)64位整數
long WP, WN, WB, WR, WQ, WK, BP, BN, BB, BR, BQ, BK;
圖1. 位圖棋盤(pán)數據結構
空的位圖棋盤(pán)在那里？由于EMPTY位圖棋盤(pán)可以通過(guò)其他12計算出來(lái)，因此聲明它會(huì )產(chǎn)生冗余數據。為計算空位圖棋盤(pán)，將12個(gè)位圖棋盤(pán)相加后求反即可。
long NOT_EMPTY=
WP | WN | WB | WR | WQ | WK |
BP | BN | BB | BR | BQ | BK ;
long EMPTY = ~NOT_EMPTY;
象棋程序運行時(shí)需要生成很多合理的走棋步驟，從中挑選最佳的。這需要完成一些計算，以確定棋盤(pán)上被攻擊的棋格，避免棋子在這些棋格上被攻擊，這樣王棋子被將的棋格以及被將死的棋格能夠確定下來(lái)。每個(gè)棋子具有不同的攻擊方式?？疾焯幚磉@些不同攻擊方式的代碼，可以看到位圖棋盤(pán)算法的一些優(yōu)缺點(diǎn)。使用位圖棋盤(pán)方案可以很優(yōu)雅的解決一些程序任務(wù)，但在另外一些方面卻不是這樣。
首先看王棋子，很簡(jiǎn)單的，王只攻擊相鄰棋格內的棋子。根據王在棋盤(pán)上的棋格的不同位置，被攻擊的有3個(gè)到8個(gè)棋格。王可能位于棋盤(pán)中間格上、邊上、或者角上，所有情況都需要代碼處理。
程序在運行時(shí)計算王的可能的64種攻擊方式，首先從基本的方式考慮，具有8種攻擊方式，然后推出特殊的情形下的攻擊方式。首先，在中間的棋格上生成掩碼，比如在第10個(gè)即B2(從A1開(kāi)始，A2,A3,到A8，然后B1,B2,…B8,依次類(lèi)推)。圖2 顯示了幾個(gè)表示掩碼的long數值。
圖2 確定王的攻擊方式
long KING_ON_B2=
1L | 1L << 1 | 1L << 2 |
1L << 7 | 1L << 9 |
1L << 15 | 1L << 16 | 1L << 17;
//王在B2時(shí)，被攻擊的格子。（Matrix注：2，3行好像不對，第2行應該是1L << 8 | 1L << 10 |，第3行也一樣）
從圖上可以看出，我們可能想將被攻擊的棋格在棋盤(pán)上左右或者上下移動(dòng)，不過(guò)向左和向右移動(dòng)時(shí)要注意邊界的影響。
SHIFTED_LEFT= KING_ON_B2 >>> 1; //左移一格
悠忽！我們將王從B2移動(dòng)到了B1(見(jiàn)圖2).象棋中一個(gè)垂直列稱(chēng)為縱線(xiàn)，將被攻擊的棋格左移一列時(shí)，從圖中可以看出最右邊的縱線(xiàn)H上的棋格并未被攻擊，相應的數字應該置0。代碼如下
final long FILE_H=
1L | (1L<<8) | (1L<<16) | (1L<<24) |
(1L<<32) | (1L<<40) | (1L<<48) | (1L<<56);
//王左移到A2時(shí)，被攻擊的棋格
KING_ON_A2= (KING_ON_B2 >>> 1) & ~FILE_H;
相應的，向右移的計算方式如下：
KING_ON_B3= (KING_ON_B2 >>> 1) & ~FILE_A;
向上和向下移動(dòng)的版本如下：
KING_ON_B1= MASK_KING_ON_B2 << 8;
KING_ON_B3= MASK_KING_ON_B2 >>> 8;
實(shí)際上，我們可以避免使用硬編碼的方式來(lái)獲取王攻擊棋格的64種可能情況，同時(shí)，也希望避免使用數組，因此，此處我們就不構建王攻擊棋格的64個(gè)元素數組了。 一種替代方案是使用64路的switch語(yǔ)句——代碼看起來(lái)不漂亮，不過(guò)可以很好的完成工作。
下面來(lái)看看“兵”，與每方僅有一個(gè)王不同，棋盤(pán)上總共有8個(gè)兵?？梢詤⒄丈厦嬗嬎阌嬎阃醯墓羝甯竦姆椒ê苋菀椎挠嬎愠鏊?個(gè)兵的攻擊棋格。注意，兵只能攻擊對角線(xiàn)上相鄰的棋格。如果向上或者向下移動(dòng)兵，相應數值要移動(dòng)8位，如果是左右移動(dòng)，相應數值要移動(dòng)1位。因此在對角線(xiàn)上數值要移動(dòng)7(8-1)位或者9(8+1)位
PAWN_ATTACKS=
((WP << 7) & ~RANK_A) & ((WP <<9) & ~RANK_H)
圖 3. 白方兵的攻擊棋格
無(wú)論棋盤(pán)上有個(gè)兵，無(wú)論兵在棋盤(pán)那個(gè)的位置上，上面代碼都有效。Robert Hyatt，Crafty程序的作者，稱(chēng)上面的算法為位并行運算(bit-parallel operation)，它同時(shí)計算出了多個(gè)棋子的信息。位并行表達式功能強大，在你自己的程序中應該作為關(guān)鍵技術(shù)應用。進(jìn)而，如果使用了很多位并行運算，那么這些運算可能是進(jìn)行位運算優(yōu)化的良好的候選。
作為對比，考慮如何使用數組來(lái)表達兵的攻擊方式
for (int i=0; i<56; i++)
{
if (board[i]= WHITE_PAWN)
{
if ((i+1) % 8 != 0) pawnAttacks[i+9]= true;
if ((i+1) % 8 != 1) pawnAttacks[i+7]= true;
}
}
上面代碼中，幾乎對整個(gè)棋盤(pán)進(jìn)行循環(huán)，速度不快?？梢灾匦戮帉?xiě)代碼，標記各個(gè)兵的位置，對每個(gè)兵的位置循環(huán)確定攻擊位置，而不需要對棋格進(jìn)行循環(huán)。不過(guò)，這樣使用位集方法，程序中還是會(huì )有更多的字節需要運行。
棋子馬的計算方式與王和兵相近。同上面處理王的情形相同，可以使用一個(gè)預先計算出來(lái)的表來(lái)確定馬的攻擊棋格。由于每方具有多于一個(gè)馬，因此計算馬的攻擊棋格的運算在技術(shù)上也是位并行運算。不過(guò)，現實(shí)中每方不大可能擁有多于兩個(gè)的馬，所以沒(méi)有什么實(shí)踐意義(選手可以選擇提升兵為馬，就擁有了多于兩個(gè)馬。實(shí)際上不大可能。譯注：此處請參考國際象棋規則)。
棋子象、軍(車(chē))、后都可以在棋盤(pán)上移動(dòng)多步。雖然它們各自的可能攻擊棋格都是一樣的，但實(shí)際的攻擊取決于在各自的攻擊路線(xiàn)上的棋子。為確定合理的移動(dòng)方式，必須單獨處理攻擊路線(xiàn)上的每個(gè)棋格。這是最壞的情況，也沒(méi)有可能的位并行算法可以使用，這樣不得不同數組方式一樣處理每個(gè)棋格。另外，使用位圖棋盤(pán)訪(fǎng)問(wèn)一個(gè)個(gè)棋格同使用數組訪(fǎng)問(wèn)棋格相比更笨拙(例如，易出錯)。
使用位圖棋盤(pán)的優(yōu)勢就是可以使用掩碼處理許多常見(jiàn)的象棋程序中的任務(wù)。拿棋子象來(lái)說(shuō)， 想確定有多少個(gè)對手的兵在象的可能多步攻擊范圍(圖4中，棋盤(pán)上的顏色)內。圖4 演示了這個(gè)攻擊掩碼問(wèn)題。
圖4 . 有多少個(gè)兵在紅色方格上
位圖棋盤(pán)模式的優(yōu)勢和不足國際象棋規則相當復雜，這也意味著(zhù)用位圖棋盤(pán)方法來(lái)處理這些規則時(shí)有優(yōu)勢也有不足。使用位圖棋盤(pán)處理某些規則很快，處理另外一些時(shí)就比較慢。上面已經(jīng)給出了使用位圖棋盤(pán)方法的低效代碼片斷，位圖棋盤(pán)算法并不是魔法粉，什么都可以高效實(shí)現?？梢韵胂笠环N與國際象棋非常相近的游戲(可能有不同的棋子), 應用位集運算會(huì )導致相反的效果或者根本不需要這樣復雜。使用位集運算進(jìn)行優(yōu)化必須經(jīng)過(guò)審慎的考慮。
一般來(lái)說(shuō)，位運算具有如下的優(yōu)勢和不足：
優(yōu)勢：· 占用內存少
· 具有高效的拷貝、設值、比較運算等
· 位并行運算的可能
不足: · 難于調試
· 訪(fǎng)問(wèn)單獨位的復雜性，易出錯
· 難于擴展
· 不符合面向對象的風(fēng)格
· 不能處理所有的任務(wù)；需要大量的工作
位圖棋盤(pán)模式的概括為概括上面的象棋例子，可以將棋盤(pán)的水平和縱向的位置想象為兩個(gè)獨立的變量或者屬性，這需要8x8一共64位來(lái)表示。另外，需要12層——每個(gè)棋子用一層表示。位圖棋盤(pán)方案的擴展方式有兩種：1)使用更多的位來(lái)擴展棋盤(pán)，添加更多的棋格 2)使用更多的層來(lái)增加棋子。實(shí)際對弈每方有64位的最大限制。但是假設我們擁有一個(gè)128位的JVM, 里面的具有128位的doublelong類(lèi)型，有了這128位，棋盤(pán)上就有了足夠的空間來(lái)在同一層中擺放黑白雙方的16個(gè)兵(8*8*2=128)。如此可以減少需要的層數量，并且可能簡(jiǎn)化一些難以理解的運算，但是卻會(huì )增加處理單獨一方兵的運算的復雜度并降低其速度。所有的Java位運算都會(huì )操作基本類(lèi)型的所有位。數據在自己所在層內僅使用本身的各位進(jìn)行位運算或者函數調用時(shí)，效率會(huì )高一些。使用位并行運算處理層內的所有位的速度比處理其中一些位的速度要快。對于增加的64位，我們可以獲得一些巧妙的使用方法，但是我們不希望將12個(gè)棋子也混合進(jìn)來(lái)。
如果在同一層內使用多于2個(gè)變量，也可以同時(shí)改變一層的所有變量?？紤]圖5中表示的3D tic-tac-toe(譯注：google)游戲，3個(gè)軸向的每個(gè)軸向的上面可能有3變量，一共有3*3*3一共27個(gè)可能值。這樣對局的每方需要使用一個(gè)32位的位集合。
圖 5. 3D tic-tac-toe 游戲的位模型
進(jìn)一步，串聯(lián)多個(gè)64位集合可以用于實(shí)現Conway生命游戲(Conway’s Game of Life, 見(jiàn)圖6)，一個(gè)在大的柵格上進(jìn)行的模擬游戲。 游戲中新單元的生死由相鄰單元的數量確定，游戲在一代代的單元繁衍中進(jìn)行。當一個(gè)死去單元的周?chē)哂?個(gè)生存單元時(shí)會(huì )復活。 一個(gè)單元的相鄰單元中沒(méi)有生存的或者僅有一個(gè)生存的，這個(gè)單元就死亡了(由于寂寞)。具有多于三個(gè)相鄰生存單元的單元也會(huì )死亡(由于人口擁擠)。相鄰單元的出生(復活)、生活，死亡，會(huì )對當前單元的狀態(tài)造成很多改變。圖6中顯示了一個(gè)生命構造圖，它會(huì )不斷繁衍，生存下去，從而通過(guò)柵格。使用下面描述的算法我們可以生成模擬生存過(guò)程的下一步：
1. 首先，與象棋游戲相似，除主柵格外另外聲明8個(gè)柵格層，每層表示某單元格的八個(gè)相鄰單元格中的一個(gè)。通過(guò)移位運算計算相鄰單元格的生存數量(某些移位數據必須從相鄰的位中獲得)。
2. 已經(jīng)有了八個(gè)層次，需要計算每個(gè)單元格的運算和，聲明9個(gè)額外的位集合來(lái)表示這些結果。比如，位集合變量SUM_IS_0到SUM_IS_8。這里可以使用遞歸算法，先計算2層的，然后計算3層、4層......直道第8層。
3. 獲得相鄰單元格生存數量后，可以容易的應用游戲規則產(chǎn)生單元格的下一代。
統計各層表示的相鄰單元格生存數量
//S0表示“和為0”，其余類(lèi)似
//L1 表示“第一層”，其余類(lèi)似
//Look at just the first two layers: 層1和層2
S0= ~(L1 | L2);
S1= L1 ^ L2;
S2= L1 & L2;
//Now look at the third layer:第3層
S3 = L3 & S2;
S2 = (S2 & ~L3) | (S1 & L3);
S1 = (S1 & ~L3) | (S0 & L3);
S0 = S0 & ~L3;
//The fourth layer.第4層
S4 = S3 & L4;
S3 = (S3 & ~L4) | (S2 & L4);
S2 = (S2 & ~L4) | (S1 & L4);
S1 = (S1 & ~L4) | (S0 & L4);
S0 = S0 & ~L4;
//Repeat this pattern up to the 8th layer.重復此模式直到第8層
計算8層的全部代碼有42行，如果需要也可以增加些。不過(guò)這42行代碼有些優(yōu)點(diǎn)，其中沒(méi)有使用邏輯判斷——邏輯判斷會(huì )降低處理器的速度， 代碼明了簡(jiǎn)單，可以通過(guò)即時(shí)(JIT)或者熱部署(Hotspot)Java編譯器的編譯。最重要的是，對于全部64個(gè)單元格所需要的數值，是通過(guò)并行計算獲得的。
圖 6. 生命游戲的模型
與非游戲應用相比，位運算在游戲等應用中更容易得到應用。其原因是游戲應用如象棋的數據模型中位與位之間具有豐富的關(guān)系。象棋的數據模型具有12層64位的位集，合計共764位。768位中的每位基本上都同其余各位有一定形式的關(guān)聯(lián)。在商業(yè)應用中，信息通常不具有這樣緊密的關(guān)系。
結論思想開(kāi)放的程序員，可能在任何問(wèn)題領(lǐng)域中應用位運算。然而，在特定情形下應用位運算合適與否取決于開(kāi)發(fā)者的判斷。老實(shí)說(shuō)，可能根本就不需要使用這些技巧。不過(guò)，上面提到的方法在特定Java應用可能正是優(yōu)化程序所需要的。如果不是這樣，也可以使用這些方法以非常hacking的方式解決一些問(wèn)題，同時(shí)迷惑你的朋友們！
享受位運算的快樂(lè )吧！
資源 ·onjava.com:
onjava.com·Matrix-Java開(kāi)發(fā)者社區:
http://www.matrix.org.cn/·
本文的代碼·
Hacker‘s Delight 一書(shū)的鏈接·
Eclipse的字節碼查看插件Glen Pepicelli 是一位軟件專(zhuān)家.他和他的狗生活在紐約州北部地區.
