Bit array

Bits as booleans

Even though booleans can only represent two values (true of false), the bool type takes 1 byte of memory. That is a waste of memory. One way to represent booleans in a memory efficient way is to use the bits of variables. Let us say we define a variable of unsigned char type, on a machine with a byte size of one octet, to 0. Then, the value of the variable in binary is 00000000b. If we consider each bit to be a boolean, then all 8 booleans equal false. If we set the value of the variable to 2, then its value in binary is 01000000b. In that case, there are 7 booleans set to false and 1 (The seventh (From the right) bit) set to true. If we see that variable as an array of booleans (bits) with a size of 8 elements, then all its elements equal false, except the element at index 6 which equals true.

By seeing variables as arrays of bits (booleans), we can represent 8 booleans with only 1 byte (If the size of a byte is 1 octet).

Testing if a bit equals 1 (true)

Let us say we want to test if the fourth bit of an unsigned char variable is set (equals 1). We can achieve that by setting all the bits, except the fourth one, to zero and then test if the variable equals 0. If it equals 0, then the bit equals 0, otherwise 1. How do we set only specific bits to 0? Using what is called bitmasks and the bitwise operators. If use the operator & (AND operator) with a value, which all bits are set to 0, as right operand, no matter the value of the left operand, the result will be zero. Right? The idea is to execute an AND operation (using the & operator) with the variable from which we want to test the bit as left operand and a binary number which all bits are set to zero except the bit a the position the bit we want to test is (This is the bitmask).

Here is an example where we test the fourth and sixth bit (From the right) of a variable:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream> int main() { unsigned char var = 219; // 219 in binary: 1101 1011 // Sets the bitmask to test the fourth bit. unsigned char bitmask = 8; // 8 in binary: 0000 1000 unsigned char result = var & bitmask; /* 1101 1011 & 0000 1000 = 0000 1000 */ /* The result is the value of the bitmask (Does not equal 0). That means the fourth bit of var equals 1. */ std::cout << (int) result << std::endl; /* The number 8 is printed in the console. */ // Changes the bitmask to test the sixth bit bitmask = 32; // 32 in binary: 0010 0000 result = var & bitmask; /* 1101 1011 & 0010 0000 = 0000 0000 */ /* The result is 0 so the sixth bit of var equals 0. */ std::cout << (int) result << std::endl; /* The number 0 is printed in the console. */ return 0; }

Merging two bit arrays

By using the | operator (OR operator) on 2 variables, the resulting value will have a bit set to 1 at each position where the bit a that position is set in at least one of the operands and its other bits unset. That means using the | operator on two bit arrays will return an array with the true bits of each array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream> // Defining bitmasks // If the first bit equals 1, that means the person knows coding. const unsigned char CAN_CODE = 1, // 1 in binary: 0000 0001 // If the second bit equals 1, it means the person knows how to draw. CAN_DRAW = 2; // 2 in binary: 0000 0010 int main() { // Can neither code nor draw. unsigned char talents = 0; // 0 in binary: 0000 0000. // Can code. talents = CAN_CODE; // Value in binary: 0000 0001. // Can code and draw. talents = CAN_CODE | CAN_DRAW; // Value in binary: 0000 0011. /* The instruction: talents & CAN_CODE Returns a non-zero (non-false) value if the first bit of talents is set. */ if(talents & CAN_CODE) std::cout << "Knows coding.\n"; /* The instruction: talents & CAN_ DRAW Returns a non-zero (non-false) value if the second bit of talents is set. */ if(talents & CAN_DRAW) std::cout << "Knows drawing.\n"; talents = CAN_DRAW; // Value in binary: 0000 0010. /* The instruction: talents & CAN_CODE Returns a non-zero (non-false) value if the first bit of talents is set. */ if(talents & CAN_CODE) std::cout << "Knows coding.\n"; else std::cout << "Does not know coding.\n"; return 0; }

In practice

Here, we will see an example where the bits of variables are used to represent booleans. In that example, the bits (booleans) are used to store information about a character of a role play game.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream> // Bitmasks const unsigned char KNIGHT = 1, // 1 in binary: 0000 0001 SPEAKS_ELFIC = 2, // 2 in binary: 0000 0010 KNOWS_FORGING = 4, // 4 in binary: 0000 0100 KNOWS_MAGIC = 8, // 8 in binary: 0000 1000 DEFEATED_DRAGON = 16, // 16 in binary: 0001 0000 EVIL = 32; // 32 in binary: 0010 0000 int main() { // The first hero is a knight and he is evil. unsigned char caracteristics = KNIGHT | EVIL; // Value in binary: 0010 0001 // The second hero speaks elfic, he knows magic and he defeated a dragon. unsigned char caracteristics2 = SPEAKS_ELFIC | KNOWS_MAGIC | DEFEATED_DRAGON; // Value in binary: 0001 1010 if(caracteristics & DEFEATED_DRAGON) std::cout << "The hero number 1 have defeated a dragon!\n"; else std::cout << "The hero number 1 have not defeated any dragon!\n"; if(caracteristics2 & DEFEATED_DRAGON) std::cout << "The hero number 2 have defeated a dragon!\n"; else std::cout << "The hero number 2 have not defeated any dragon!\n"; if(caracteristics2 & SPEAKS_ELFIC) std::cout << "The hero number 2 knows the elfic language.\n"; else std::cout << "The hero number 2 does not know the elfic language.\n"; if(caracteristics & KNOWS_FORGING) std::cout << "The hero number 1 knows forging.\n"; else std::cout << "The hero number 1 does not know forging.\n"; return 0; }