Using bit fields and bit masks in C

The C programming language offers many ways to arrange data in memory. If you need to combine several variables, one way to do it is with a data structure, like this for an x,y coordinate system:

typedef struct {
  float x;
  float y;
} coord_t;

This allows you to use the structure like a single variable, comprised of two float variables, x and y. The typedef statement associates the struct of two float elements to a new variable “type” called coord_t.

#include <stdio.h>

typedef struct {
  float x;
  float y;
} coord_t;

int main()
{
  coord_t pos;

  pos.x = 1.4;
  pos.y = 3.1;

  printf("the x,y coordinate is %f,%f\n", pos.x, pos.y);

  return 0;
}

But using a structure like this isn’t always the right approach. Fortunately, C offers another option to combine data using bit fields and bit masks. To use bit fields, you need to think like a computer and remember that data is stored in bits, and each bit is a one or a zero.

Bits and binary

Let’s say you were writing a chess game in C. One way to track the pieces on the board is by defining a structure that defines each possible piece on the board, and its color, so every square contains an element from that structure. For example, you might have a structure that looks like this:

struct chess_pc {
   int piece;
   int is_black;
}

With this programming structure, your program will know what piece is in every square and its color. You can quickly identify if the piece is a pawn, rook, knight, bishop, queen, or king—and if the piece is black or white. But there’s a more straightforward way to track the same information while using less data and memory. Rather than storing a structure of two int values for every square on a chessboard, we can store a single int value and use binary bit fields and masks to identify the pieces and color in each square.

To apply bit fields and bit masks to this problem, let’s start by listing the possible chess pieces and assigning a number to each. I’ll help us along to the next step by representing the number in its binary form, the way the computer would track it:

• (0 = 00000000) empty
• (1 = 00000001) pawn
• (2 = 00000010) rook
• (3 = 00000011) knight
• (4 = 00000100) bishop
• (5 = 00000101) queen
• (6 = 00000110) king

To list all pieces on a chessboard, we only need the three bits that represent (from right to left) the values 1, 2, and 4. For example, the number 6 is binary 110. All of the other bits in the binary representation of 6 are zeroes.

And with a bit of cleverness, we can use one of those extra always-zero bits to track if a piece is black or white. We can use the number 8 (binary 00001000) to indicate if a piece is black. If this bit is 1, it’s black; if it’s 0, it’s white. That’s called a bit field, which we can pull out later using a binary mask.

Storing data in bit fields

To write a chess program using bit fields and masks, we might start with these definitions:

/* this uses bits from 0000 (0) to 0110 (6) */
#define EMPTY  0
#define PAWN   1
#define ROOK   2
#define KNIGHT 3
#define BISHOP 4
#define QUEEN  5
#define KING   6

/* the bit mask for black/white is 1000 (8) */
#define BLACK  8
#define WHITE  0

/* the bit mask for the piece is 0111 (7) */
#define PIECE  7

When you assign a value to a square, such as when initializing the chessboard, you can assign a single int value to track both the piece and its color. For example, to store a black rook in position 0,0 of an array, you would use this code:

int main()
{
    square_t board[8][8]; /* 0-7 is 8 square, total is 8x8=64 squares */

    board[0][0] = BLACK | ROOK; /* 1000 | 0010 = 1010 (10) */
...

The | is a binary Or, which means the computer will combine the bits from two numbers. For every bit position, if that bit from either number is 1, the result for that bit position is also 1. Binary Or of the value BLACK (8, or binary 00001000) and the value ROOK (2, or binary 00000010) is binary 00001010, or 10:

   00001000 (8)
Or 00000010 (2)

   00001010 (10)

Similarly, to store a white pawn in position 6,0 of the array, you could use this:

int main()
{
    square_t board[8][8]; /* 0-7 is 8 square, total is 8x8=64 squares */

    board[6][0] = WHITE | PAWN; /* 0000 | 0001 = 0001 (1) */
...

This stores the value 1 because the binary Or of WHITE (0) and PAWN (1) is just 1:

   00000000 (0)
Or 00000001 (1)

   00000000 (1)

Retrieving bits with masks

During the chess game, the program will need to know what piece is in a square and its color. We can separate the piece using a binary mask.

For example, the program might need to know the contents of a specific square on the board during the chess game, such as the array element at board[5][3]. What piece is there, and is it black or white?

The binary And operator (&) combines two binary values so that for any bit position, if that bit in both numbers is 1, then the result is also 1. For example, if a piece in the board array has the value 10, we can use a bit mask to write an is_black function to determine if the piece is black or white:

int is_black(square_t sq)
{
    return (sq & BLACK); /* uses the bit mask for black/white */
}

This works because the value BLACK is 8, or binary 00001000. And in the C programming language, any non-zero value is treated as True, and zero is always False. So is_black(board[6][0]) will return a True value (8) if the piece in array element 6,0 is black and will return a False value (0) if it is white.

Putting it all together

Let’s combine everything to define an 8×8 chess board with two pieces on it, a black rook and a white pawn. We can then use the bit fields and bit masks to store and retrieve data:

#include <stdio.h>

/* could also #include <stdint.h> and use uint8_t, which is also 1 byte */
typedef unsigned char square_t; /* 1 byte */

/* this uses bits from 0000 (0) to 0110 (6) */
#define EMPTY  0
#define PAWN   1
#define ROOK   2
#define KNIGHT 3
#define BISHOP 4
#define QUEEN  5
#define KING   6

/* the bit mask for black/white is 1000 (8) */
#define BLACK  8
#define WHITE  0

/* the bit mask for the piece is 0111 (7) */
#define PIECE  7

int is_black(square_t sq)
{
    return (sq & BLACK); /* uses the bit mask for black/white */
}

int main()
{
    square_t board[8][8]; /* 0-7 is 8 square, total is 8x8=64 squares */

    board[0][0] = BLACK | ROOK; /* 1000 | 0010 = 1010 (10) */
    board[6][0] = WHITE | PAWN; /* 0000 | 0001 = 0001 (1) */

    printf("the rook at [0][0] is %d=%s\n", board[0][0],
    (is_black(board[0][0]) ? "black" : "white") );

    printf("the pawn at [6][0] is %d=%s\n", board[6][0],
    (is_black(board[6][0]) ? "black" : "white") );

    return 0;
}

If we compile and run this program, we’ll see that the rook is black and the pawn is white:

the rook at [0][0] is 10=black
the pawn at [6][0] is 1=white

Using bit fields and masks is a common method to combine data without using structures. They are worth adding to your programmer’s “tool kit.” While data structures are a valuable tool for ordered programming where you need to track related data, using separate elements to track single True or False values (such as the colors of chess pieces) is less efficient. In these cases, consider using bit fields and masks to combine your data more efficiently.