Bit Fields: Squishing Booleans Using Bitwise Operations

The problem: I wanted to let users select one or more days of the week for one of my projects.

My first reaction was to simply use an array. If the name of the day is in that list, then it would mean that the day is selected, such as:

// Monday to Thursday (example 1)
days = ["Monday", "Tuesday", "Wednesday", "Thursday"]
// Wednesday and Saturday (example 2)
days = ["Wednesday", "Saturday"]

Fast-forward 10 minutes, and I realized that, well, this was very readable, but this wasn’t really optimal. Delete operations are a pain, because I’d have to iterate over the entire list to find the day’s index, and strings would require validation somewhere down the line, which is extra work.

So I started thinking again.

Maybe if I just use the index of the array as an indicator, I could just completely forgo the strings altogether and use a boolean to determine whether each day was selected or not.

// Monday to Thursday
days = [false, true, true, true, true, false, false]
// Wednesday and Saturday
days = [false, false, false, true, false, false, true]

This is much easier to manipulate, thanks to no longer having to parse the names of the days, yet I still had an array, which is harder to persist than a single value, albeit not by much.

Nevertheless, I liked the second implementation better than the first, so I decided to continue building on it.

At this point, what I knew was that I always have 7 booleans, one for each day, and a boolean can only be true (1) or false (0), which means that technically, 7 bits is all I need to store the information necessary.

This is where bit fields comes into play. These booleans can easily be converted into a single integer, effectively merging multiple fields into a single one. This is exactly what I wanted.

Sun Mon Tue Wed Thu Fri Sat
Value 1 2 4 8 16 32 64
Mon-Thu - X X X X - -
Wed,Sat - - - X - - X

By using the logic above, we can calculate the integer value of our two examples:

  • Monday to Thursday: 0 + 2 + 4 + 8 + 16 + 0 + 0 = 30
  • Wednesday and Saturday: 0 + 0 + 0 + 8 + 0 + 0 + 64 = 72

And so Monday to Thursday can now be stored as 30 instead of ["Monday", "Tuesday", "Wednesday", "Thursday"].

To validate that we didn’t mess up, 30 converts to 11110 in binary and 72 converts to 1001000.

If you try to put the integers as-is in the table above to confirm, you’ll notice that it won’t work, and that’s normal. It’s because the table above has the lowest unit on the left rather than on the right, and when you read a number, the bigger unit is on the left.

i.e. If you read the number “427”, the digit on the right, 7, is the smallest because it only represents 7 units, while the number 2 represents 20 and the number 4 represents 400. It’s the exact same for binaries, smaller units are on the right, while the bigger units are on the left. This is why we need to reverse either the table, so that the larger units are on the left instead of the right, or the binary number itself.

To take the point above into consideration, we can simply try to place the binary representation of 30 (11110) and 72 (1001000) in the reverse order, meaning from left to right, in the same table we used earlier, and you’ll notice that not only does it match the pattern of the earlier table above, we can also use it confirm that Monday to Thursday is indeed 30 (2+4+8+16) as well as Wednesday and Saturday is 72 (8+64).

Sun Mon Tue Wed Thu Fri Sat
Value 1 2 4 8 16 32 64
Mon-Thu 0 1 1 1 1 - -
Wed,Sat 0 0 0 1 0 0 1

The code

This is the best part, in my opinion at least.

All of this may have sounded a bit complicated, but when you see how easy it is to put in practice, I’m sure you’ll be happy.

First, we need constants for our days:

const (
    Sunday    = 1 // For Go readers: you could just append "<< iota" to this line and not specify the next integers
    Monday    = 2
    Tuesday   = 4
    Wednesday = 8
    Thursday  = 16
    Friday    = 32
    Saturday  = 64

The reason why we’re using multiples of 2 is because we’re using binary, which is base 2. We want each day of the week to belong to one bit in a way that if Saturday’s bit is 1, it means it’s selected, and if it’s 0, then it’s not selected. Each day of the week is defined by whether its bit at its respective position is set to 1 or 0.

This means that, from the right (remember, smaller units are always on the right), Sunday has the first bit, Monday has the second bit, Tuesday has the third bit, and so on and so forth.

To define the magical integer that will support multiple values in a single field:

days := Monday | Tuesday | Wednesday | Thursday // integer value of days: 30

To check whether days has Tuesday in it, you must use the bitwise AND operator (&):

// This checks that the bit at the position where Tuesday should be (3rd bit from the right)
// is not set to 0. 
daysIncludeTuesday := days & Tuesday != 0 // returns true

// If you want to get into the specifics, `days & Tuesday` will return 0 if the bit is not
// set, or the value of Tuesday (4), if it is set, so you could use the following instead,
// but I think it's a lot more readable to compare it to 0.
daysIncludeTuesday := days & Tuesday == Tuesday // returns true

To add Friday to days, you need to use the bitwise OR (|) operator, just like earlier when we first created the variable days:

days = days | Friday // The integer value of days is 62 

// A lot of languages also support this syntax:
days |= Friday       // The integer value of days is 62 

// Note that performing the operation multiple times will not cause any issues.
// This why even though the code above shows two bitwise OR operations, the value
// of days is still 62. In fact, you could even do this and the value would still
// be 62:
days = days | Friday | Friday

To remove Friday from days, you need to use the bitwise NOT operator, which for some magical reason, is inconsistent across languages. Most languages (e.g. C, JavaScript) uses ~ (which is the correct sign), while others like Rust and Go use ! and ^ respectively.

Removing Friday from days in Go:

days = days & ^Friday

Removing Friday from days in most other languages:

days = days & ~Friday

To recap everything:

  • Define: days = Monday | Tuesday | Wednesday | Thursday
  • Add: days = days | Friday
  • Remove: days = days & ~Friday or days = days & ^Friday depending on the language