Creative Use of Bitwise Operators

While at the Fronteers conference watching Thomas Fuchs go through his slides, a keen member of the audience noticed his use of bitwise negation and asked what it was for. Understandable, as there is so rarely a time where bitwise operators seem necessary.

It did, however, remind me of a project that I worked on where I ended up using bitwise operators quite heavily in one particular chunk of code. It's a solution that I'm quite particular fond of.

The project was to build a calendar and place events on it. Nothing ground breaking; plenty of calendars out there. I probably could have or should have looked at existing implementations to see how they did it and while I think my approach is cool, it's quite possible that there's a better way to solve this problem (and I'd love to hear how other people have solved this).

The problem with a calendar is that events for a particular week should fit nicely together. If an event overlaps another event then it should go on a separate line. At the same time, when an event doesn't overlap, it should fit nicely into an open spot in the layout and not on a separate line each time.

In thinking about slots, I started seeing things as switches that needed to be flagged on or off and that's what had me think of bitwise operators.

I looked at a particular week and envisioned it broken up into horizontal rows of 7 blocks (one for each day of the week) and numbered from 0 to 6. All of this fit nicely into a byte of information (not that I really had to worry about that, in this case).

First, I needed to know how many slots that an event would use up. This was the easy part. Just figure out over how many days the event appeared (end date minus start date). Then, I converted this into a binary format.

var daysdiff = 4; // an event is 4 days long
var eventmask = Math.pow(2,daysdiff)-1; // 15 or 0001111

This takes the number 2 and puts it to the power of 4 and shifts it down one because we're working off a zero-based array of bits. A four day difference is converted to 15 or 0001111 in binary (see? four 1s for a four day event).

Now I needed to figure out on what day of the week it started. Then I shift the bits over the same number of day. (Picture the bits representing the days right to left instead of left to right, with Sunday being the first bit.)

eventmask <<= startdate.getDay();

The start date is just a JavaScript date object and getDay is the method that returns what day of the week the date falls on as a number between 0 and 6 to represent Sunday through Saturday respectively.

The << performs bitshifting and, combined with the equal sign, the result is assigned to the mask. If an event started on Monday, the ones would be shifted over 1 day and give us 0011110.

Now that we know where in the week the event falls, we need to apply this to a mask for the week. An empty week will have zero slots filled.

var weekmask = 0; // 0000000

Next, I needed to apply my event mask to the week mask and see if I got a result.

if ( (~weekmask & eventmask) == eventmask ) { /* apply mask */ }

The weekmask gets a bitwise NOT (~) applied to it, which flips each bit. If it was a 0, it's now a 1 and if it was a 1, it's now a 0. It then gets the eventmask applied to it with a bitwise AND (&). The AND does a comparison of each bit. If both are 0s, it's a 0. If one is a 1 and one is a 0, it becomes a 0. If both are 1s, it's a 1.

Breaking this down, the weekmask is flipped to 1111111 and then ANDed with the event mask 0011110, which should leave us with 0011110. Is this the same as the original event mask? Yes, it is. So go ahead and apply the event mask to the week mask and move on to the next event.

The event mask is applied with a bitwise OR operation. It's like the AND operator but will turn a bit into a 1 if either value has a 1.

weekmask |= eventmask;

Let's look at another example where there's an existing event already applied to the week mask for Monday. The week mask would look like 0000010. First it's flipped to 1111101 and then ANDed with the event mask, which creates 0011100. This doesn't match our original event mask so the event mask then tries to apply itself to the next slot for the week. (What I haven't mentioned up until now is that the week mask should actually be an array to represent each row of slots that that week contains. I'll demonstrate this in the final code example.)

Now we've seen where an event gets applied on an empty week and where an event gets applied when a slot is already taken. What about trying to apply an event on a week that already has an event but where they don't overlap? If I've done a decent job of explaining this, hopefully it'll already be evident.

If there's an event that has already been applied to the week mask for Friday and Saturday, we have a week mask of 1100000. It's flipped to 0011111. Our event mask of 0011110 is ANDed and gives us 0011110 which does match our original event mask. That means we can apply the event mask to the week mask with the OR operator and we get 1111110.

Here's essentially what the code would look like put together:

// looping through all events to map out for a week
var weekmask = [];
for (var i=0; i < events.length; i++) {
    var daysdiff = events[i].daysdiff; // calculated elsewhere
    var eventmask = Math.pow(2,daysdiff) - 1;
    eventmask <<= events[i].startdate.getDay();
    for (var j=0; j < weekmask.length; j++) {
       if ((~weekmask[j] & eventmask) == eventmask) break; // exit loop if found
    }
    weekmask[j] |= eventmask; // commit it
    /* draw event on calendar... */
}

To describe this code block, we loop through the events and then loop through each set of slots for a particular week. If the spot isn't found in a particular row then a new row is created and the eventmask is applied to that row.

I sometimes wonder if I created a complicated solution to a simple problem but describing this to people is fun, at the very least.