使用位欄位和掩碼寫一個國際象棋遊戲
假設你在用 C 語言寫一個國際象棋遊戲。追蹤棋盤上棋子的一種方法是定義一個結構,該結構定義了棋盤上每個可能的棋子及其顏色,因此每個格子都包含該結構中的一個元素。例如,你可以將結構定義成下面這樣:
struct chess_pc {
int piece;
int is_black;
}
有了這個數據結構,你的程序就會知道每個格子里是什麼棋子及棋子的顏色。你可以快速識別出棋子是兵、車、馬、象、後還是王,以及棋子是黑還是白。但是,有一種更直接的方法來跟蹤這些信息,同時只用更少的數據和內存。與為棋盤上的每個方格存儲兩個 int
值的結構不同,我們可以存儲單個 int
值,並使用二進位位欄位和掩碼來標識每個方格中的棋子和顏色。
比特和二進位
當使用位欄位表示數據時,我們最好像計算機一樣思考。讓我們從列出可能的棋子開始,並為每個棋子分配一個數字。讓我們進入下一個步驟,用二進位表示這個數字,也就是按照計算機追蹤它的方式。記住,二進位數是由比特組成的,比特要麼是 0,要麼是 1。
00000000:
空(0)00000001:
兵(1)00000010:
車(2)00000011:
馬(3)00000100:
象(4)00000101:
後(5)00000110:
王(6)
要列出一個棋盤上的所有棋子,我們只需要三個比特從右到左依次代表值 1、2 和 4。例如,數字 6 是二進位的 110。6 的二進位表示中的其他所有位都是 0。
一個聰明一點的方法:我們可以使用那些額外的總是為零的比特來跟蹤一個棋子是黑還是白。我們可以使用數字 8(二進位 00001000
)來表示棋子是否為黑色。如果這一位是 1,則代表該棋子是黑色;如果是 0,則代表該棋子是白色。這被稱為位欄位,稍後我們可以使用二進位掩碼將其取出。
用位欄位存儲數據
要編寫一個使用位欄位和掩碼的國際象棋程序,我們可以從以下定義開始:
/* 棋子 */
#define EMPTY 0 // 空
#define PAWN 1 // 兵
#define ROOK 2 // 車
#define KNIGHT 3 // 馬
#define BISHOP 4 // 象
#define QUEEN 5 // 後
#define KING 6 // 王
/* 棋色 */
#define BLACK 8 // 黑
#define WHITE 0 // 白
/* 掩碼 */
#define PIECE 7
當你為一個棋格賦值時,比如初始化棋盤,你可以賦一個 int
類型的值來跟蹤棋子及其顏色。例如,要在棋盤的 0,0
位置存儲棋子黑車,你可以使用下面的代碼:
int board[8][8];
..
board[0][0] = BLACK | ROOK;
|
是二進位「或」(OR
)操作符,這意味著計算機將合併兩個數字的比特。對於每個比特的位置,如果任意一個數字的比特為 1,該位置比特的結果也是 1。BLACK
的值(8,即二進位下的 00001000
)和 ROOK
的值(2,即二進位下的 00000010
)的二進位或結果是二進位下的 00001010
,即 10:
00001000 = 8
OR 00000010 = 2
________
00001010 = 10
類似地,要在棋盤的 6,0
位置存儲一個白色兵,你可以這樣做:
board[6][0] = WHITE | PAWN;
這樣存儲的值就是 WHITE
(0)和 PAWN
(1)的二進位或的結果,也即是 1。
00000000 = 0
OR 00000001 = 1
________
00000001 = 1
用掩碼獲取數據
在下棋過程中,程序需要知道棋格中的棋子和它的顏色。我們可以使用二進位掩碼來分離這部分。
舉個例子,程序可能需要知道棋局中棋盤上特定棋格的內容,例如位於 board[5][3]
的數組元素。這個是什麼棋子,是黑的還是白的?為了識別棋子,使用二進位「與」(AND
)操作符將元素的值與掩碼 PIECE
結合起來:
int board[8][8];
int piece;
..
piece = board[5][3] & PIECE;
二進位「與」(AND
)操作符(&
)將兩個二進位值結合,這樣對於任意位,如果兩個數字中的那個位都是 1,那麼結果也是 1。例如,如果 board[5][3]
的值是 11(二進位下的 00001011
),那麼 11 和 掩碼 PIECE
(7,二進位下的 00000111
)二進位與的結果為二進位下的 00000011
,也即 3。這代表馬,馬的值是 3。
00001011 = 11
AND 00000111 = 7
________
00000011 = 3
解析棋子的顏色是一個簡單的事情,只需要將棋子的值與 BLACK
位欄位進行二進位與操作。比如,你可以寫一個名為 is_black
的函數來確定棋子是黑還是白:
int
is_black(int piece)
{
return (piece & BLACK);
}
之所以可以這樣,是因為 BLACK
的值為 8(二進位下的 00001000
)。在 C 語言中,任何非零值都被視為 True
,零總是 False
。所以如果 5,3
處的棋子是黑色的,則 is_black(board[5][3])
返回 True 值(8);如果是白色的,則返回 False 值(0)。
位欄位
使用位欄位和掩碼是不使用結構組合數據的常用方法。它們值得被程序員收藏到「工具包」中。雖然數據結構對於需要跟蹤相關數據的有序編程是一種有價值的工具,但是使用單獨的元素來跟蹤單個的開或閉值(例如棋子的顏色)的效率較低。在這些情況下,可以考慮使用位欄位和掩碼來更高效地組合數據。
via: https://opensource.com/article/21/8/binary-bit-fields-masks
作者:Jim Hall 選題:lujun9972 譯者:FYJNEVERFOLLOWS 校對:wxy
本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive