快速小測試：如何重寫下面的語句？要求不使用條件判斷語句交換兩個常量的值。
if (x == a) x= b;
  else x= a;

答案：
x= a ^ b ^ x;

//此處變量x等于a或者等于b
字符^是邏輯異或XOR運算符。上面代碼為什么能工作呢？使用XOR運算符，一個變量執(zhí)行2次異或運算與另一個變量，總是返回變量自身。


雖然Java位操作的魔術(shù)不是很普及，但是深入研究此技術(shù)有助于改善程序性能。在作者的機器配置下進行基準測試，重寫版本需5.2秒，使用邏輯判斷的版本需5.6秒。(測試代碼參見資源部分)。減少使用判斷語句通常可以提高在現(xiàn)代多管道處理器上的程序性能。

對于Java程序員來說，特別有益的是一些用來處理所謂bitsets位集的技巧。 Java語言中的原始類型int和long也可被視為32位或64位的位集合?？梢越M合這些簡單的結(jié)構(gòu)來表示大型數(shù)據(jù)結(jié)構(gòu)，比如數(shù)組。另外，還有一些特定的運算(bit-parallel 并行位運算),可以有效的將多個不同的運算壓縮為一個運算。使用以bit為單位的細粒度數(shù)據(jù),而不是以integer整數(shù)為運算單位，我們會發(fā)現(xiàn)——對于integer整數(shù)來說有時進行的僅僅一步運算，如果使用bit位作為運算單位實際上可能進行了許多操作?？梢哉J為Java語言中的位并行運算是軟件多通路技術(shù)的一種應(yīng)用。

高級對弈程序如Crafty(使用C語言編寫)使用了特殊的數(shù)據(jù)結(jié)構(gòu)——bitboard位圖棋盤來表示棋子的位置，這樣比使用數(shù)組的速度快很多。與C程序員相比，Java程序員更不應(yīng)該使用數(shù)組。與C語言中數(shù)組的高效實現(xiàn)相比，Java語言中的數(shù)組實現(xiàn)(雖然提供了邊界檢查以及GC機制等額外功能)效率低下。為比較使用整數(shù)方案以及使用數(shù)組方案的性能，在作者機器(Windows XP, AMD Athlon, 熱部署Java虛擬機？)上進行的簡單測試顯示使用數(shù)組方案的運行時間是使用整數(shù)方案的160%，并且此處未考慮無用單元回收(garbage collection)對性能的影響。在某些情況下，可以使用整數(shù)位集替代數(shù)組。

下面會探討一下從匯編語言時代就存在的古董技巧，同時特別關(guān)注這些技巧在位集上的應(yīng)用。Java作為可移植語言本身對位運算提供了良好的支持。進一步，Java Tiger版本的API中又添加了一些用于位處理的方法。

典型Java環(huán)境下的位優(yōu)化
Java程序運行在機器和操作系統(tǒng)之上，但是與機器和操作系統(tǒng)中充斥的位運算不同，Java程序基本上不包含大量的位運算。雖然現(xiàn)代CPU提供了特殊的位操作指令，不過在Java語言中無法執(zhí)行這些特殊指令。JVM僅提供了有符號移位、無符號移位、位異或(bitewise XOR)、位或(bitwise OR)、位并(bitwise AND)以及位否(bitwise NOT)等位運算。有意思的是，并不僅僅是Java沒有提供額外的位運算，很多匯編程序員編寫操作CPU的程序時，也會發(fā)現(xiàn)缺少同樣的位運算指令。兩類程序員在位運算上的境遇其實一樣。匯編程序員不得不通過軟件模擬來實現(xiàn)這些指令，同時盡可能的保證效率。 Tiger版本的Java中許多方法也是通過使用純java代碼來模擬實現(xiàn)這些指令的。

進行性能微調(diào)操作的C程序員可能會審查實際產(chǎn)生的匯編代碼、參考目標CPU的優(yōu)化器手冊、統(tǒng)計代碼執(zhí)行的指令周期數(shù)目等方式來改善程序性能。與之相對，在Java程序里進行這樣的底層優(yōu)化的一個實際問題是無法確定優(yōu)化的效果。Sun公司的Java虛擬機規(guī)范(JVM spec)未給出某特定操作執(zhí)行的相對速度。可以將自己認為執(zhí)行速度快的代碼一部分再一部分的在Java虛擬機中執(zhí)行，結(jié)果只能令人震驚——速度沒有提高甚至優(yōu)化部分可能降低原來程序性能。 Java虛擬機可能會攪亂破壞你做出的優(yōu)化，也可能在內(nèi)部對一般的代碼優(yōu)化。 在任何情況下，通過JVM實現(xiàn)優(yōu)化, 即使編譯過后的程序提供這樣的支持，相應(yīng)得優(yōu)化也需要進行基準測試。

標準的查看字節(jié)碼的工具是JDK中包含的javap命令。Eclipse的使用者也可以利用由Andrei Loskutov開發(fā)的字節(jié)碼查看插件。 Sun的網(wǎng)站上提供了JVM設(shè)計和指令集合的參考書的在線版本。注意，每個Java虛擬機內(nèi)包含兩種類型的內(nèi)存. 一種是棧(stack)，用來存儲局部原始類型變量和表達式；另一種是堆(heap),用來存儲對象和數(shù)組。堆內(nèi)存儲的對象會被無用單元回收機制處理，而棧具有固定大小的內(nèi)存塊。雖然大多數(shù)程序僅僅使用了?？臻g的很小部分，JVM規(guī)范聲明用戶可以認為棧至少有64k大小。請注意JVM可以被認為是一個32位或者64位的機器，所以字節(jié)byte以及位數(shù)少的原始類型的運算不大可能比整數(shù)int的運算更快。

2的補數(shù)
Java語言中，所有的整數(shù)原始類型都是有符號數(shù)字，使用2的補數(shù)形式表示。要操作這些原始類型，我們需要理解一些相關(guān)理論。

2的補數(shù)分成兩種：非負補數(shù)和負補數(shù)。補數(shù)的最高位，也是符號位，在一般系統(tǒng)上在最左邊。非負補數(shù)的此位是0?？梢院唵蔚膹淖蟮接易x取這些普通的非負補數(shù)，將他們轉(zhuǎn)換到任意進制的整數(shù)。如果符號位設(shè)置為1，此數(shù)就是負數(shù)，除去符號位的右邊位集合與符號位一起表示此負數(shù)。

有兩種方法來考察負的補數(shù)。 首先，可以從可能的最小負數(shù)數(shù)起直到-1，比如，8位字節(jié)，從最小的10000000(-128)開始，然后是10000001(-127),一直到11111111(-1)。另外一種考慮負的補數(shù)的方式有些古怪，當存在符號位時，用前面都是1后面跟著個0來代替前面都是0后面跟著個1的方式。然而，你最后需要從結(jié)果中減去1。 比如11111111時符號位后面跟著7個1，(視為10000000)表示負零(-0),然后添加(也可以認為是減去)1，得到-1，同樣11111110(視為10000001，加上1是10000010)是-2，11111101(視為10000010，是-2，然后減去1)是-3，以此類推。

感覺上有些怪，我們可以混合位運算符號和數(shù)學(xué)運算符號來進行多種操作。比如將x變換為-x，可以表示為對x按位求反，然后加1，即(~x)+1，具體運算過程見下表。




布爾標記和標準布爾位集
如下的位標記模式(bit flag pattern)是很普通的技術(shù)常識，在圖形用戶界面GUI程序的公用API中得到了廣泛應(yīng)用。呵呵，我們可能正在為資源有限設(shè)備如蜂窩電話或者PDA編寫一個Java GUI程序。對GUI中每個構(gòu)件如按鈕(button)和下拉列表(drop-down list)都擁有一些Boolean選擇項標記。使用位標記，可以將許多選擇項安排到一個變量中。

//The constants to use with our GUI widgets:  GUI構(gòu)件使用的選擇項常量
final int visible      = 1 << 0;  //  1 可見？
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 可移動？
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選擇項的位標記組合成一個參數(shù)，在一次符值操作中全部傳遞，這基本上不需要什么時間。API可能會聲明，每個組件在某時僅能使用邊界樣式A、邊界樣式B、邊界樣式C、或者邊界樣式D中的一種，那么可以通過使用掩碼(mask)來獲取對應(yīng)的4位，然后檢查這4位中至多有一個1。下面代碼中的小技巧稍后會解釋。

int illegalOptionCombo=           //不合法的組合框選項
  2+ 64+ 128+ 512;               // 10 11000010
        
int borderOptionMask=             //邊界選項掩碼 
  64+ 128+ 256+ 512;             // 11 11000000
        
int temp= illegalOptionCombo &   //獲取4個邊界選項的所有的1位
  borderOptionMask               // 10 11000000
        
int rightmostBit=                 //獲得temp的最右邊的1
  temp & ( -temp );              // 00 01000000

如果變量temp與rightMostBit不相等，那么表明temp必然含有多個1位。因為如果rightMostBit為0那么temp也應(yīng)該是0，否則temp僅有一個1位。

if (temp != rightmostBit)
  throw new IllegalArgumentException();

上面的示例是個玩具程序?，F(xiàn)實中，AWT和Swing使用了位標記模式，但是使用方式的不連貫。java.awt.geom.AffineTransform類中使用了很多，java.awt.Font 和java.awt.InputEvent也使用了。

通用的位運算以及JDK 1.5的方法
為了更好的應(yīng)用位運算，需要掌握所謂的標準技巧，也就是那些可以應(yīng)用的位運算方法。J2SE 5.0 Tiger版本內(nèi)增加了一些新的位運算API。如果你使用的是老版本，只要剪切粘貼那些方法實現(xiàn)到你的代碼中。最近由Henry S. Warren,Jr編寫的書籍Hacker‘s Delight內(nèi)包含了很多關(guān)于位運算算法的資料。

下表展示了一些運算，這些運算可以通過一行代碼或者通過一次調(diào)用API方法實現(xiàn)



欲了解上面API方法的運行時間，可以閱讀JDK中相應(yīng)的源碼。一些方法可能更難以理解一些。所有方法都在Hacker‘s Delight一書中進行了解釋。這些API方法基本上都是一行代碼或者很少幾行代碼實現(xiàn)的，比下面給出的的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的位圖棋盤模式）

下面部分，就像烈酒伏特加和變幻莫測的鏡子一樣，其中的位運算變得很復(fù)雜。
在冷戰(zhàn)發(fā)展到頂點的時期，國際象棋是計算機科學(xué)的一個研究熱點。原蘇聯(lián)和美國各自獨立的提出了新的象棋數(shù)據(jù)結(jié)構(gòu)——位圖棋盤。美國團隊——Slate和Atkin，基于Chess 4.x軟件出版了《人類和機器的國際象棋技能》一書，其中有一章討論了位圖棋盤算法，這可能是最早的關(guān)于位圖棋盤算法的印刷品。 原蘇聯(lián)團隊，包括Donskoy以及其他人員，開發(fā)了使用位圖棋盤算法的程序Kaissa。這兩個軟件在世界范圍都具有勝利性的競爭力。

在討論位圖棋盤算法前，我們先來看看使用Java語言(或其他許多語言)表示棋盤的標準方法。

//棋盤上64個格子所有可能狀態(tài)的整數(shù)枚舉

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個元素的整數(shù)數(shù)組表示64個格子

int[] board= new int[64];

使用數(shù)組方法很直觀，相反，位圖棋盤算法的數(shù)據(jù)結(jié)構(gòu)是使用12個64位的位集表示，每個表示一種類型的棋子(每方6種棋子，共12種)。 如下圖，視覺上看上去好像是一個堆在另一個的上面。

//為棋盤聲明12個64位整數(shù)

long WP, WN, WB, WR, WQ, WK, BP, BN, BB, BR, BQ, BK;

圖1. 位圖棋盤數(shù)據(jù)結(jié)構(gòu)

空的位圖棋盤在那里？由于EMPTY位圖棋盤可以通過其他12計算出來，因此聲明它會產(chǎn)生冗余數(shù)據(jù)。為計算空位圖棋盤，將12個位圖棋盤相加后求反即可。

long NOT_EMPTY=
  WP | WN | WB | WR | WQ | WK |
  BP | BN | BB | BR | BQ | BK  ;
long EMPTY = ~NOT_EMPTY;

象棋程序運行時需要生成很多合理的走棋步驟，從中挑選最佳的。這需要完成一些計算，以確定棋盤上被攻擊的棋格，避免棋子在這些棋格上被攻擊，這樣王棋子被將的棋格以及被將死的棋格能夠確定下來。每個棋子具有不同的攻擊方式?？疾焯幚磉@些不同攻擊方式的代碼，可以看到位圖棋盤算法的一些優(yōu)缺點。使用位圖棋盤方案可以很優(yōu)雅的解決一些程序任務(wù)，但在另外一些方面卻不是這樣。

首先看王棋子，很簡單的，王只攻擊相鄰棋格內(nèi)的棋子。根據(jù)王在棋盤上的棋格的不同位置，被攻擊的有3個到8個棋格。王可能位于棋盤中間格上、邊上、或者角上，所有情況都需要代碼處理。

程序在運行時計算王的可能的64種攻擊方式，首先從基本的方式考慮，具有8種攻擊方式，然后推出特殊的情形下的攻擊方式。首先，在中間的棋格上生成掩碼，比如在第10個即B2(從A1開始，A2,A3,到A8，然后B1,B2,…B8,依次類推)。圖2 顯示了幾個表示掩碼的long數(shù)值。


圖2  確定王的攻擊方式

long KING_ON_B2=
1L       | 1L << 1  | 1L << 2  |
1L << 7  |            1L << 9  |
1L << 15 | 1L << 16 | 1L << 17;
//王在B2時，被攻擊的格子。（Matrix注：2，3行好像不對，第2行應(yīng)該是1L << 8  |       1L << 10  |，第3行也一樣）

從圖上可以看出，我們可能想將被攻擊的棋格在棋盤上左右或者上下移動，不過向左和向右移動時要注意邊界的影響。

SHIFTED_LEFT= KING_ON_B2 >>> 1;  //左移一格

悠忽！我們將王從B2移動到了B1(見圖2).象棋中一個垂直列稱為縱線，將被攻擊的棋格左移一列時，從圖中可以看出最右邊的縱線H上的棋格并未被攻擊，相應(yīng)的數(shù)字應(yīng)該置0。代碼如下

final long FILE_H=
1L       |  (1L<<8) | (1L<<16) | (1L<<24) |
(1L<<32) | (1L<<40) | (1L<<48) | (1L<<56);

//王左移到A2時，被攻擊的棋格

KING_ON_A2= (KING_ON_B2 >>> 1) & ~FILE_H;

相應(yīng)的，向右移的計算方式如下：

KING_ON_B3= (KING_ON_B2 >>> 1) & ~FILE_A; 

向上和向下移動的版本如下：

KING_ON_B1= MASK_KING_ON_B2 <<  8;
KING_ON_B3= MASK_KING_ON_B2 >>> 8;

實際上，我們可以避免使用硬編碼的方式來獲取王攻擊棋格的64種可能情況，同時，也希望避免使用數(shù)組，因此，此處我們就不構(gòu)建王攻擊棋格的64個元素數(shù)組了。 一種替代方案是使用64路的switch語句——代碼看起來不漂亮，不過可以很好的完成工作。

下面來看看“兵”，與每方僅有一個王不同，棋盤上總共有8個兵?？梢詤⒄丈厦嬗嬎阌嬎阃醯墓羝甯竦姆椒ê苋菀椎挠嬎愠鏊?個兵的攻擊棋格。注意，兵只能攻擊對角線上相鄰的棋格。如果向上或者向下移動兵，相應(yīng)數(shù)值要移動8位，如果是左右移動，相應(yīng)數(shù)值要移動1位。因此在對角線上數(shù)值要移動7(8-1)位或者9(8+1)位

PAWN_ATTACKS=
((WP << 7) & ~RANK_A) & ((WP <<9) & ~RANK_H) 

圖 3. 白方兵的攻擊棋格

無論棋盤上有個兵，無論兵在棋盤那個的位置上，上面代碼都有效。Robert Hyatt，Crafty程序的作者，稱上面的算法為位并行運算(bit-parallel operation)，它同時計算出了多個棋子的信息。位并行表達式功能強大，在你自己的程序中應(yīng)該作為關(guān)鍵技術(shù)應(yīng)用。進而，如果使用了很多位并行運算，那么這些運算可能是進行位運算優(yōu)化的良好的候選。

作為對比，考慮如何使用數(shù)組來表達兵的攻擊方式

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;
  }
}

上面代碼中，幾乎對整個棋盤進行循環(huán)，速度不快。可以重新編寫代碼，標記各個兵的位置，對每個兵的位置循環(huán)確定攻擊位置，而不需要對棋格進行循環(huán)。不過，這樣使用位集方法，程序中還是會有更多的字節(jié)需要運行。

棋子馬的計算方式與王和兵相近。同上面處理王的情形相同，可以使用一個預(yù)先計算出來的表來確定馬的攻擊棋格。由于每方具有多于一個馬，因此計算馬的攻擊棋格的運算在技術(shù)上也是位并行運算。不過，現(xiàn)實中每方不大可能擁有多于兩個的馬，所以沒有什么實踐意義(選手可以選擇提升兵為馬，就擁有了多于兩個馬。實際上不大可能。譯注：此處請參考國際象棋規(guī)則)。

棋子象、軍(車)、后都可以在棋盤上移動多步。雖然它們各自的可能攻擊棋格都是一樣的，但實際的攻擊取決于在各自的攻擊路線上的棋子。為確定合理的移動方式，必須單獨處理攻擊路線上的每個棋格。這是最壞的情況，也沒有可能的位并行算法可以使用，這樣不得不同數(shù)組方式一樣處理每個棋格。另外，使用位圖棋盤訪問一個個棋格同使用數(shù)組訪問棋格相比更笨拙(例如，易出錯)。
使用位圖棋盤的優(yōu)勢就是可以使用掩碼處理許多常見的象棋程序中的任務(wù)。拿棋子象來說， 想確定有多少個對手的兵在象的可能多步攻擊范圍(圖4中，棋盤上的顏色)內(nèi)。圖4 演示了這個攻擊掩碼問題。


圖4 . 有多少個兵在紅色方格上

位圖棋盤模式的優(yōu)勢和不足
國際象棋規(guī)則相當復(fù)雜，這也意味著用位圖棋盤方法來處理這些規(guī)則時有優(yōu)勢也有不足。使用位圖棋盤處理某些規(guī)則很快，處理另外一些時就比較慢。上面已經(jīng)給出了使用位圖棋盤方法的低效代碼片斷，位圖棋盤算法并不是魔法粉，什么都可以高效實現(xiàn)?？梢韵胂笠环N與國際象棋非常相近的游戲(可能有不同的棋子), 應(yīng)用位集運算會導(dǎo)致相反的效果或者根本不需要這樣復(fù)雜。使用位集運算進行優(yōu)化必須經(jīng)過審慎的考慮。

一般來說，位運算具有如下的優(yōu)勢和不足：

優(yōu)勢：
·        占用內(nèi)存少
·        具有高效的拷貝、設(shè)值、比較運算等
·        位并行運算的可能

不足:
·        難于調(diào)試
·        訪問單獨位的復(fù)雜性，易出錯
·        難于擴展
·        不符合面向?qū)ο蟮娘L(fēng)格
·        不能處理所有的任務(wù)；需要大量的工作

位圖棋盤模式的概括
為概括上面的象棋例子，可以將棋盤的水平和縱向的位置想象為兩個獨立的變量或者屬性，這需要8x8一共64位來表示。另外，需要12層——每個棋子用一層表示。位圖棋盤方案的擴展方式有兩種：1)使用更多的位來擴展棋盤，添加更多的棋格 2)使用更多的層來增加棋子。實際對弈每方有64位的最大限制。但是假設(shè)我們擁有一個128位的JVM, 里面的具有128位的doublelong類型，有了這128位，棋盤上就有了足夠的空間來在同一層中擺放黑白雙方的16個兵(8*8*2=128)。如此可以減少需要的層數(shù)量，并且可能簡化一些難以理解的運算，但是卻會增加處理單獨一方兵的運算的復(fù)雜度并降低其速度。所有的Java位運算都會操作基本類型的所有位。數(shù)據(jù)在自己所在層內(nèi)僅使用本身的各位進行位運算或者函數(shù)調(diào)用時，效率會高一些。使用位并行運算處理層內(nèi)的所有位的速度比處理其中一些位的速度要快。對于增加的64位，我們可以獲得一些巧妙的使用方法，但是我們不希望將12個棋子也混合進來。

如果在同一層內(nèi)使用多于2個變量，也可以同時改變一層的所有變量?？紤]圖5中表示的3D tic-tac-toe(譯注：google)游戲，3個軸向的每個軸向的上面可能有3變量，一共有3*3*3一共27個可能值。這樣對局的每方需要使用一個32位的位集合。


圖 5. 3D tic-tac-toe 游戲的位模型

進一步，串聯(lián)多個64位集合可以用于實現(xiàn)Conway生命游戲(Conway’s Game of Life, 見圖6)，一個在大的柵格上進行的模擬游戲。 游戲中新單元的生死由相鄰單元的數(shù)量確定，游戲在一代代的單元繁衍中進行。當一個死去單元的周圍具有3個生存單元時會復(fù)活。 一個單元的相鄰單元中沒有生存的或者僅有一個生存的，這個單元就死亡了(由于寂寞)。具有多于三個相鄰生存單元的單元也會死亡(由于人口擁擠)。相鄰單元的出生(復(fù)活)、生活，死亡，會對當前單元的狀態(tài)造成很多改變。圖6中顯示了一個生命構(gòu)造圖，它會不斷繁衍，生存下去，從而通過柵格。使用下面描述的算法我們可以生成模擬生存過程的下一步：

1.        首先，與象棋游戲相似，除主柵格外另外聲明8個柵格層，每層表示某單元格的八個相鄰單元格中的一個。通過移位運算計算相鄰單元格的生存數(shù)量(某些移位數(shù)據(jù)必須從相鄰的位中獲得)。
2.        已經(jīng)有了八個層次，需要計算每個單元格的運算和，聲明9個額外的位集合來表示這些結(jié)果。比如，位集合變量SUM_IS_0到SUM_IS_8。這里可以使用遞歸算法，先計算2層的，然后計算3層、4層......直道第8層。
3.        獲得相鄰單元格生存數(shù)量后，可以容易的應(yīng)用游戲規(guī)則產(chǎn)生單元格的下一代。

統(tǒng)計各層表示的相鄰單元格生存數(shù)量

//S0表示“和為0”，其余類似
//L1 表示“第一層”，其余類似

//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.重復(fù)此模式直到第8層

計算8層的全部代碼有42行，如果需要也可以增加些。不過這42行代碼有些優(yōu)點，其中沒有使用邏輯判斷——邏輯判斷會降低處理器的速度， 代碼明了簡單，可以通過即時(JIT)或者熱部署(Hotspot)Java編譯器的編譯。最重要的是，對于全部64個單元格所需要的數(shù)值，是通過并行計算獲得的。


圖 6. 生命游戲的模型

與非游戲應(yīng)用相比，位運算在游戲等應(yīng)用中更容易得到應(yīng)用。其原因是游戲應(yīng)用如象棋的數(shù)據(jù)模型中位與位之間具有豐富的關(guān)系。象棋的數(shù)據(jù)模型具有12層64位的位集，合計共764位。768位中的每位基本上都同其余各位有一定形式的關(guān)聯(lián)。在商業(yè)應(yīng)用中，信息通常不具有這樣緊密的關(guān)系。

結(jié)論
思想開放的程序員，可能在任何問題領(lǐng)域中應(yīng)用位運算。然而，在特定情形下應(yīng)用位運算合適與否取決于開發(fā)者的判斷。老實說，可能根本就不需要使用這些技巧。不過，上面提到的方法在特定Java應(yīng)用可能正是優(yōu)化程序所需要的。如果不是這樣，也可以使用這些方法以非常hacking的方式解決一些問題，同時迷惑你的朋友們！
享受位運算的快樂吧！

資源
·:
·Matrix-Java開發(fā)者社區(qū):http://www./
·本文的代碼
·Hacker‘s Delight 一書的鏈接
·Eclipse的字節(jié)碼查看插件


Glen Pepicelli 是一位軟件專家.他和他的狗生活在紐約州北部地區(qū).

本頁面地址:

→投票評分

     非常好 還行 一般 扔雞蛋          總得分：5 / 投票人次：1

→用戶評論列表

#6363 評論作者： hilton2005 發(fā)表時間：2005-11-25 01:15

牛b,tongyangkanbudong !

#6320 評論作者： cleverpig 發(fā)表時間：2005-11-24 10:23

呵呵,文章不錯。就是在圖KING_ON_B2確定王的攻擊方式:

long KING_ON_B2=
1L       | 1L << 1  | 1L << 2  |
1L << 7  |            1L << 9  |
1L << 15 | 1L << 16 | 1L << 17;
//王在B2時，被攻擊的格子。（Matrix注：2，3行好像不對，第2行應(yīng)該是1L << 8  |       1L << 10  |，第3行也一樣）

和圖FILE_H的代碼：

final long FILE_H=
1L       |  (1L<<8) | (1L<<16) | (1L<<24) |
(1L<<32) | (1L<<40) | (1L<<48) | (1L<<56);

中好像存在著錯誤。
因為由在FILE_H中使用的是1L逐個遞增左移8，看上去好像表示的是FILE_A而不是FILE_H。
而在KING_ON_B2中，我的認識和作者相同，應(yīng)該是：

long KING_ON_B2=
1L       | 1L << 1  | 1L << 2  |
1L << 8  |            1L << 10  |
1L << 16 | 1L << 17 | 1L << 18;