使用位字段和掩码写一个国际象棋游戏

使用位字段和掩码写一个国际象棋游戏

使用位字段和掩码是不用数据结构组合数据的常用方法。

假设你在用 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

本文由 LCTT 原创编译,Linux中国 荣誉推出