Schreiben Sie ein Schachspiel mit Bitfeldern und Masken
Die Verwendung von Bitfeldern und Masken ist eine gängige Methode zum Kombinieren von Daten ohne Verwendung von Strukturen.
Nehmen wir an, Sie schreiben ein Schachspiel in C. Eine Möglichkeit, die Figuren auf dem Brett zu verfolgen, besteht darin, eine Struktur zu definieren, die jede mögliche Figur auf dem Brett und ihre Farbe definiert, sodass jedes Quadrat ein Element aus dieser Struktur enthält. Beispielsweise könnte Ihre Struktur so aussehen:
struct chess_pc {
int piece;
int is_black;
}Mit dieser Programmierstruktur weiß Ihr Programm, welches Teil sich in jedem Quadrat befindet und welche Farbe es hat. Sie können schnell erkennen, ob es sich bei der Figur um einen Bauern, einen Turm, einen Springer, einen Läufer, eine Dame oder einen König handelt – und ob die Figur schwarz oder weiß ist. Es gibt jedoch eine einfachere Möglichkeit, dieselben Informationen zu verfolgen und dabei weniger Daten und Speicher zu verbrauchen. Anstatt eine Struktur aus zwei int-Werten für jedes Feld auf einem Schachbrett zu speichern, können wir einen einzelnen int-Wert speichern und binäre Bitfelder verwenden und Masken zur Identifizierung der Teile und Farben in jedem Quadrat.
Bits und Binärdateien
Bei der Verwendung von Bitfeldern zur Darstellung von Daten ist es hilfreich, wie ein Computer zu denken. Beginnen wir damit, die möglichen Schachfiguren aufzulisten und ihnen jeweils eine Nummer zuzuordnen. Ich helfe uns beim nächsten Schritt, indem ich die Zahl in ihrer binären Form darstelle, so wie der Computer sie verfolgen würde. Denken Sie daran, dass Binärzahlen aus Bits bestehen, die entweder Null oder Eins sind.
00000000:leer (0)00000001:Bauer (1)00000010:Turm (2)00000011:Ritter (3)00000100:Bischof (4)00000101:Königin (5)00000110:König (6)
Um alle Figuren auf einem Schachbrett aufzulisten, benötigen wir nur die drei Bits, die (von rechts nach links) die Werte 1, 2 und 4 darstellen. Die Zahl 6 ist beispielsweise binär 110. Alle anderen Bits in der binären Darstellung von 6 sind Nullen.
Und mit etwas Geschick können wir eines dieser zusätzlichen Bits, die immer Null haben, verwenden, um zu verfolgen, ob ein Stück schwarz oder weiß ist. Wir können die Zahl 8 (binär 00001000) verwenden, um anzuzeigen, ob ein Stück schwarz ist. Wenn dieses Bit 1 ist, ist es schwarz; wenn es 0 ist, ist es weiß. Das nennt man ein Bitfeld, das wir später mithilfe einer binären Maske herausziehen können.
Speichern von Daten mit Bitfeldern
Um ein Schachprogramm mit Bitfeldern und Masken zu schreiben, könnten wir mit diesen Definitionen beginnen:
/* game pieces */
#define EMPTY 0
#define PAWN 1
#define ROOK 2
#define KNIGHT 3
#define BISHOP 4
#define QUEEN 5
#define KING 6
/* piece color (bit-field) */
#define BLACK 8
#define WHITE 0
/* piece only (mask) */
#define PIECE 7Wenn Sie einem Quadrat einen Wert zuweisen, beispielsweise beim Initialisieren des Schachbretts, können Sie einen einzelnen int-Wert zuweisen, um sowohl die Figur als auch ihre Farbe zu verfolgen. Um beispielsweise einen schwarzen Turm an Position 0,0 eines Arrays zu speichern, würden Sie diesen Code verwenden:
int board[8][8];
..
board[0][0] = BLACK | ROOK;Der | ist ein binäres ODER, was bedeutet, dass der Computer die Bits von zwei Zahlen kombiniert. Wenn für jede Bitposition das Bit aus einer beliebigen Zahl 1 ist, ist das Ergebnis für diese Bitposition ebenfalls 1. Binäres ODER des Werts BLACK (8 oder binär 00001000) und der Wert ROOK (2, oder binär 00000010) ist binär 00001010, oder 10:
00001000 = 8
OR 00000010 = 2
________
00001010 = 10Um einen weißen Bauern an Position 6,0 des Arrays zu speichern, könnten Sie auch Folgendes verwenden:
board[6][0] = WHITE | PAWN;Dadurch wird der Wert 1 gespeichert, da das binäre ODER von WHITE (0) und PAWN (1) nur 1 ist:
00000000 = 0
OR 00000001 = 1
________
00000001 = 1Mit Masken Daten rausholen
Während des Schachspiels muss das Programm wissen, welche Figur sich in einem Feld befindet und welche Farbe sie hat. Wir können das Stück mithilfe einer Binärmaske trennen.
Beispielsweise muss das Programm während des Schachspiels möglicherweise den Inhalt eines bestimmten Felds auf dem Brett kennen, beispielsweise das Array-Element bei board[5][3]. Welches Stück ist da und ist es schwarz oder weiß? Um die Schachfigur zu identifizieren, kombinieren Sie den Wert des Elements mit der PIECE-Maske mithilfe des binären UND:
int board[8][8];
int piece;
..
piece = board[5][3] & PIECE;Der binäre UND-Operator (&) kombiniert zwei Binärwerte, sodass für eine beliebige Bitposition das Ergebnis ebenfalls 1 ist, wenn das Bit in beiden Zahlen 1 ist , wenn der Wert von board[5][3] 11 ist (binärer 00001011), dann ist das binäre UND von 11 und die Maske PIECE (7, oder binärer 00000111) ist binär 00000011, oder 3. Dies ist ein Ritter, der ebenfalls den Wert 3 hat.
00001011 = 11
AND 00000111 = 7
________
00000011 = 3Die Trennung der Farbe des Teils erfolgt ganz einfach durch die Verwendung von binärem AND mit dem Wert und dem Bitfeld BLACK. Sie könnten dies beispielsweise als Funktion namens is_black schreiben, um zu bestimmen, ob ein Stück entweder schwarz oder weiß ist:
int
is_black(int piece)
{
return (piece & BLACK);
}Dies funktioniert, weil der Wert BLACK 8 oder binär 00001000 ist. Und in der Programmiersprache C wird jeder Wert ungleich Null als wahr behandelt, und Null ist immer falsch. is_black(board[5][3]) gibt also einen True-Wert (8) zurück, wenn das Teil im Array-Element 5,3 schwarz ist, und gibt einen False-Wert zurück (0) wenn es weiß ist.
Bitfelder
Die Verwendung von Bitfeldern und Masken ist eine gängige Methode zum Kombinieren von Daten ohne Verwendung von Strukturen. Es lohnt sich, sie zum „Werkzeugkasten“ Ihres Programmierers hinzuzufügen. Während Datenstrukturen ein wertvolles Werkzeug für die geordnete Programmierung sind, bei der Sie zusammengehörige Daten verfolgen müssen, ist die Verwendung separater Elemente zum Verfolgen einzelner Ein- oder Aus-Werte (z. B. der Farben von Schachfiguren) weniger effizient. Erwägen Sie in diesen Fällen die Verwendung von Bitfeldern und Masken, um Ihre Daten effizienter zu kombinieren.