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.

Google Calendar

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).

Slots for a week

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.

Published November 12, 2009 · Updated November 12, 2009
Categorized as JavaScript
Short URL: http://snook.ca/s/962

Conversation

24 Comments · RSS feed
Tyler Gillies said on November 12, 2009

I love the design of your blog

Philip Sturgeon said on November 12, 2009

This looks awesome, but I've read it twice and it will need at least third before I know what the hell is going on.

Bookmarked for a later read. Thanks dude!

Adriaan said on November 12, 2009

wow, this is an excellent explanation...I found it really interesting.

Clinton Montague said on November 12, 2009

Brilliant use of bitwise ops! Up until around a year ago, I thought they were obscurities for 40 year old bearded nerds who still live with their mum, but I'm seeing more and more uses for them all the time. This I think has to be one of the most elegant. Thanks!

MySchizoBuddy said on November 12, 2009

can this technique be used to find the last Monday of the month, or the second Tuesday of an year

Ethan Dunham said on November 12, 2009

I have no idea what you just said.

Jeff L said on November 12, 2009

I echo the comments of Philip and Ethan.

jdbartlett said on November 12, 2009

Wow, great post! Thanks!

myschizobudd: I think a more traditional Date-object based solution would work better to find the last day of a particular month. Snook isn't saying that bitwise operators are a good way to handle all date calculations, he's just using a calendar events as an example of practical application of bitwise operators. Not to get too off-topic, but the code you're looking for would go something like this:

var i = new Date(2009, 11, 0);
while (i.getDay() != 2) i.setDate(i.getDate() - 1);

(At the end of which, i is the last Tuesday of November 2009.)

Robert Ames said on November 12, 2009

Interesting mechanism I saw the other day was in python, overriding the __ror__ (right "or") operator to allow you to use certain objects as if they were pipelines in unix shell.

class blah:
    __ror__( self, other ):
        return self.foo + other.foo
3 == new blah(1) | new blah(2)

...but it wasn't as simple as addition, instead they used it as filters for HTML: new Template() | strip_html | replace_fields | add_header | add_footer

...very interesting abuse of the language.

Nicolas said on November 12, 2009

Nice post!

Since you're dealing with powers of 2 I think you could replace

    Math.pow(2,daysdiff)-1;

for

   (1 >> daysdiff) -1;

and it should run faster also.

Bruno Daniel said on November 12, 2009

This, ladies and gentlemen, is code-fu at it's best.

Jonathan Snook said on November 12, 2009

@Nicolas: The bitshift operator would be << and not >> but that works perfectly. Thanks for the suggestion!

jero said on November 12, 2009

Some time ago I tried to do something very similar, but i gave up and used a less sophisticated approach. I'll bookmark this for future reference. thanks.

travisjbeck said on November 12, 2009

hey Jonathan, any chance of you posting this project anywhere? I've been working on the exact same problem.

Jonathan Snook said on November 12, 2009

@Travis: I wish I could but being a client project, I can't. This article was really just meant to take an abstract look at the problem to demonstrate the use of bitwise operators. You'll still have to figure out how to draw the events on the screen and handle all the fun edge cases—and there are plenty!

Thomas said on November 13, 2009

Wow impressive piece of code! I really like this approach, as far as I get it lol :-)

Your blog design looks quite impressive too by the way!

Christopher Penkin said on November 15, 2009

Great post. Like the solution.

Rhys said on November 16, 2009

It is a complicated solution to a simple problem, but bloody elegant nonetheless. I like it.

Alan said on November 16, 2009

I don't know the language you're using (Ruby?)...it's been years since I wrote any code. Does the language you're using provide a "do while" loop? It seems it would be a bit more elegant than that "break" you have in your for loop.

Revv Up said on November 17, 2009

Cool stuff...but most of it gone above my head..
ll need to do some homework..

Jonathan Snook said on November 17, 2009

@Alan: the language is JavaScript and breaks work just fine. I could modify the loop test if I wanted but it would mean adding variables to the mix. do/whiles just change where the validation step occurs; it doesn't solve the problem of having to test for something to get out of the loop.

Alan said on November 17, 2009

Thanks for taking the time to reply. I feel pretty silly having made that post for an assortment of reasons. Anyway, very interesting things you're doing.

Caleb said on November 19, 2009

Geekgasmic!

I just knew that one day a CompSci degree would be applicable to web development...

Dinesh said on February 03, 2011

Elegant and Excellent solution.

Sorry, comments are closed for this post. If you have any further questions or comments, feel free to send them to me directly.