Motivation
Say we have a collection of mutually exclusive options to pick from and we wanted to store those options selected by the user. A great way to store this is by using bit masks. In this article we are going to describe what they are and how to use them properly.
Code
Say we wanted to write a calendar program that handled recurring meetings. Bit masks would be a way to store the days of the week that a meeting occurs on.
We’ll start with what the code looks like, and then we’ll give a more detailed explanation later. First, we’ll start with an enum to store the days of the week:
enum DayOfWeek
{
DAY_MONDAY = 1,
DAY_TUESDAY = 2,
DAY_WEDNESDAY = 4,
DAY_THURSDAY = 8,
DAY_FRIDAY = 16,
DAY_SATURDAY = 32,
DAY_SUNDAY = 64
};
Then, if we want to know if a meeting happens on a given day, we can test it with the following code:
if ((day & DAY_MONDAY) == DAY_MONDAY)
{
cout << "Meeting occurs on Monday" << endl;
}
Where the day variable would be an int and would store the day (or days) of the week that the meeting occurs on. We could then use a similar pattern to test other days of the week. Here’s Friday for example:
if ((day & DAY_FRIDAY) == DAY_FRIDAY)
{
cout << "Meeting occurs on Friday" << endl;
}
Setting the day variable is fairly easy as well. If the meeting only occurs on Monday, then it would be set like this:
int day = DAY_MONDAY;
However, if the meeting occurred on Mondays, Wednesdays, and Fridays, then it would be set like this:
int day = DAY_MONDAY | DAY_WEDNESDAY | DAY_FRIDAY;
Explanation
To start the explanation, let’s use an alternative definition and then build towards the code that is above. So, our alternative definition is going to have seven Boolean values. Each value indicates whether or not the meeting occurs on the specified day. One possible implementation might look like this:
class DayOfWeek
{
public:
DayOfWeek(bool monday, bool tuesday, bool wednesday,
bool thursday, bool friday, bool saturday, bool sunday)
{
Monday = monday;
Tuesday = tuesday;
Wednesday = wednesday;
Thursday = thursday;
Friday = friday;
Saturday = saturday;
Sunday = sunday;
}
bool Monday;
bool Tuesday;
bool Wednesday;
bool Thursday;
bool Friday;
bool Saturday;
bool Sunday;
};
If we wanted to create a meeting that only occurs on Monday, we could do it like this:
DayOfWeek day = DayOfWeek(true, false, false, false, false, false, false);
Here the monday variable is set to true and all of the others are set to false. Therefore, the meeting only occurs on Mondays.
Testing whether or not the meeting occurred on Monday would be fairly easy, we could just use the Monday property:
if (day.Monday)
{
cout << "Meeting occurs on Monday" << endl;
}
So, this class looks pretty straight-forward and easy to use, what’s the problem? It isn’t very efficient. bool values are typically stored using 8 to 32 bits under the covers. So, this will take up at least 8 bits * 7 values = 56 bits. Compared to the enum above which only takes up 32 bits. Additionally, issues like serialization and computations (i.e. merging Meetings) will be more difficult using the bool representation.
Conceptually, the enum and the bool representation are very similar. The enum uses binary values to determine whether or not the meeting occurs on a given day:
Name | Value | Binary |
DAY_MONDAY | 1 | 0000001 |
DAY_TUESDAY | 2 | 0000010 |
DAY_WEDNESDAY | 4 | 0000100 |
DAY_THURSDAY | 8 | 0001000 |
DAY_FRIDAY | 16 | 0010000 |
DAY_SATURDAY | 32 | 0100000 |
DAY_SUNDAY | 64 | 1000000 |
The value column is the decimal representation of the value that we used when defining the enum. The meaning of these values isn’t very clear until we convert them into binary [1]. Once they are in binary, it becomes much clearer that the bits are used much like a bool. The value on the far right represents whether or not the meeting occurs on Monday. (1 = true, 0 = false) Then the values slowly move to the left for each day. Notice that each day has its own bit to store whether or not the meeting occurs on that day.
Therefore, when working with bit masks, it is much better to think of them in their binary representation rather than their decimal representation. This is especially true when manipulating them. Let’s start by determining whether or not a meeting occurs on a given day. We did that with the following if statement:
if ((day & DAY_MONDAY) == DAY_MONDAY)
{
cout << "Meeting occurs on Monday" << endl;
}
The & symbol stands for “bitwise and” [2], so let’s look what is going on at the bit (binary) level. To do this, let’s take the first part of the expression and store it to a temporary variable:
int result = (day & DAY_MONDAY);
Now let’s assume that day = 31 or 0011111 in binary (all week days). So, the computation would look like this:
0011111 (day)
& 0000001 (DAY_MONDAY)
---------
0000001 (result)
To compute this, we go through the corresponding bits in each number and compare them with an and operation. Since the bit on the far right is the only bit that is set to 1 in both values, that is the only one that is set to 1 in the result.
Finally, we use the result and compare that to the value that we used in the bitwise and computation to see if the meeting occurred on the given day.
As another example, let’s see what happens if we compare DAY_WEDNESDAY and DAY_MONDAY:
0000100 (DAY_WEDNESDAY)
& 0000001 (DAY_MONDAY)
---------
0000000 (result)
So, the result is 0000000, which means that it won’t be equal to DAY_MONDAY (0000001), so the if statement will be false. That’s exactly what we wanted.
The last operation that was shown earlier was for meetings that happened on multiple days. To do this we used the “bitwise or” operation or the | symbol:
int day = DAY_MONDAY | DAY_WEDNESDAY | DAY_FRIDAY;
Again, looking at the binary representation, things become much clearer:
0000001 (DAY_MONDAY)
| 0000100 (DAY_WEDNESDAY)
| 0010000 (DAY_FRIDAY)
---------
0010101 (day)
So, now we compare the corresponding bits in the given values using the or operation. This would now give us a day value that corresponds to having a meeting on Mondays, Wednesdays, and Fridays.
Random Note: If Statement
An if statement only evaluates to false when the integer value being passed to it is zero. So, it is possible to do:
if (day & DAY_MONDAY)
Instead of:
if ((day & DAY_MONDAY) == DAY_MONDAY)
The == is commonly done because it makes the code slightly clearer as far as variable types goes. In the first case an integer is being passed to the if statement. In the second case, two integers are being compared with the equals operator, which produces a Boolean that is passed to the if statement. Since we typically think of if statements in terms of Booleans instead of integers, this is a little clearer. (And we are not relying on the somewhat secret fact that only zero evaluates to false and everything else is true.)
However, if we dropped the ==, we could do some more checks like this one:
int weekend = DAY_SATURDAY | DAY_SUNDAY;
if (day & weekend)
{
cout << "Meeting occurs on a weekend!" << endl;
}
To see why this would work, walk through the example where day is DAY_SATURDAY. For fun, you could also compare that with a check like the one that we used before and see why this doesn’t work:
// BUG: This does NOT check to see if an occurrence of the
// meeting happens on a weekend
if ((day & weekend) == weekend)
Random Note: DAY_NONE
Another complication would be storing an explicit value for a meeting that doesn’t occur. (Not super helpful in our example, but if the bit mask was representing something else, it might be helpful.) So, something like this:
enum DayOfWeek
{
DAY_NONE = 0,
DAY_MONDAY = 1,
DAY_TUESDAY = 2,
DAY_WEDNESDAY = 4,
DAY_THURSDAY = 8,
DAY_FRIDAY = 16,
DAY_SATURDAY = 32,
DAY_SUNDAY = 64
};
When using it, you need to be a little careful, because you can’t use the above pattern for an if statement:
if ((day & DAY_NONE) == DAY_NONE)
If you did, then the if statement would always evaluate to true. Here’s an example using DAY_MONDAY:
0000001 (DAY_MONDAY)
& 0000000 (DAY_NONE)
---------
0000000 (result)
So, the result is 0000000 which is equal to DAY_NONE. Unfortunately, that’s probably not what we wanted, since we probably didn’t want DAY_MONDAY to be equal to DAY_NONE.
To do a comparison with DAY_NONE, the best way would be just to do it directly:
if (day == DAY_NONE)
Simple enough. However, this might lead to wondering why we didn’t do something like this before:
if (day == DAY_MONDAY)
{
cout << "Meeting occurs on Monday and only Monday" << endl;
}
We could, but this changes the meaning of the if statement slightly. Now we are checking if the meeting occurs on Monday and only on Monday. So a value like the one that we used earlier of DAY_MONDAY | DAY_WEDNESDAY | DAY_FRIDAY would be false with the new check. So, it really depends on what we are looking to check.
If you don’t follow that completely, work through a couple of examples looking at the binary values. Then it should become much clearer what is going on.
Random Note: Addition
When working with bit masks, you want to use binary operations like bitwise and, or, and xor. As opposed to working with addition or subtraction. To see this, let’s work through an example. Say we want to make sure that we meet every Monday. So, we want to take in a set of days that we meet and add Mondays. Doing something like this would be a bad idea:
// Bad Idea!
day = day + DAY_MONDAY;
Even though it might seem like it would work in a couple of cases. Take the case of day = DAY_WEDNESDAY. In this case, the code above would appear to work just fine. However, in the case when day was all weekdays (DAY_MONDAY | DAY_TUESDAY | DAY_WEDNESDAY | DAY_THURSDAY | DAY_FRIDAY), the result of the addition would be DAY_SATURDAY. Not exactly what we intended. To see this, look at what’s going on in binary:
0011111 (day)
+ 0000001 (DAY_MONDAY)
---------
0100000 (result)
Now we could fix the situation by doing an if statement and only adding Monday if it did not exist, but there is an easier way. If we use the bitwise or operator it will give the desired result:
day = day | DAY_MONDAY;
Now Monday will be added to the meeting days if it does not exist and even if it does, nothing bad will happen. We’ll still meet on Monday.
0011111 (day)
| 0000001 (DAY_MONDAY)
---------
0011111 (result)
Conclusion
Bit masks are very powerful and very efficient. They come up every once in a while and can be a great tool to solve many problems. When using them, you should switch over to thinking in binary, and then what is going on will be much clearer. Hopefully now you know how to use them and have some ideas of when they might be beneficial.
Footnotes
[1] In the binary conversion, we only kept 7 bits. Really the value would be 32 bits long, however the extra zeros don’t add anything other than a potential for confusion.
[2] & and && are two different operators. & is “bitwise and”, and && is “logical and”.
