How Fast Can the Number of Days in a Month Be Calculated with JS?

An Exercise in Futility

After reading Curtis McEnroe’s article about creating a formula to calculate the number of days in a month, inspired by JS byte-slashers like 219 Byte Tron, 140 Byte Tetris, and the work over at p01, I got to thinking about a way to make it more compact. First off, here is what Curtis came up with:

function curtisMcEnroe(x) {
    return 28 + (x + Math.floor(x / 8)) % 2 + 2 % x + 2 * Math.floor(1 / x);
}

For future reference, the body of that function is 47 bytes.

Like Curtis, I will be considering handling leap years out of scope

My first thought was to go bitwise. I started out by laying out a table of month indices, the length of each month, and the binary representations of those two numbers.

Index Length Index (Binary) Length (Binary)
1 31 0001 0001 1111
2 28 0010 0001 1100
3 31 0011 0001 1111
4 30 0100 0001 1110
5 31 0101 0001 1111
6 30 0110 0001 1110
7 31 0111 0001 1111
8 31 1000 0001 1111
9 30 1001 0001 1110
10 31 1010 0001 1111
11 30 1011 0001 1110
12 31 1100 0001 1111

I stared at it for a bit and got nowhere, so I decided to take a systematic approach. I constructed the K-map below, where the two MSBs of the month index are the bits on the top and the two LSBs are on the side. The K-map was populated with the LSB of the month length and the - character represents a “Don’t Care”.

0001 11 10
00 - 0 1 1
01 1 1 - 0
11 1 1 -0
10 0 0 - 1

From the K-map, the following expression can be derived, where w is the MSB and z is the LSB:

Fantastic. I could XOR the MSB and LSB of the index to get the LSB of the length. I could then OR that with 0b00011110 (30) which would tell me if a month is 30 or 31 days.

function bitwise(x) {
    return 30 | (x >> 3 ^ x) & 1;
}

That left the body of the function at only 14 bytes. The logical next step was to carry that approach on to the next LSB. If you take a look at the index/length table above, you’ll notice that there every length except the 28 has a 1 in that position. That makes using a K-map useless and left me with a few options:

  1. I could use three right shifts and three ANDs to determine if the index is 2
  2. I could use an equality operator to determine if the index is 2
  3. I could store the result of the calculation for the LSB then use that and the index to determine the next LSB

This is the point at which I started to deviate from course. The obvious choice is option #2 but that would be too easy and I’d have to rename my function to something else because I would no longer be exclusively using bitwise operators. I couldn’t have that. Suffice it to say, I went forward with option #3.

The function for option #2 is at the bottom of the page. It ended up being only 25 bytes but interestingly was about twice as slow as option #31.

This next step wasn’t done with a systematic approach like the first. Going back to the staring at the numbers technique, I noticed that the first operation would spit out 30 for February and that February’s index was the only index that produced a 30 from the first operation that had a 0 in the first and third bit postiions. That meant that all I had to do to identify which month had a length of 28 was to check if there was a 0 in the first and third bit position of the index an the LSB of the output from the previous operation. That gave me this:

function bitwise(x) {
    var y;
    return (y = 30 | (x >> 3 ^ x) & 1) ^ (~(x >> 2 | x | y) & 1) << 1
}

which is only 43 bytes! Success. That is definitely more compact but I had an inkling that it would faster too. I popped the two functions into jsPerf and it turns out it was. That gave me another rabbit hole to go down.

How fast can I make this thing?

Like bitwise operators seemed like an obvious choice for shrinking the function, so to did lookup tables for making it faster. I simply put the length of each month in an array with padding element at the front so that I could still use the 1-based index without a subtraction operation. I came up with this:

var t = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
function lookup(x) {
    return t[x];
}

It was fast but not that fast1. I thought back to the index/length table and remembered that the only bits that changed for the length were the two LSBs. And since there are only 12 months (13 with a padding month), I could fit all of those sets of bits into a single 32-bit integer. That gave me the bits 11 10 11 10 11 11 10 11 10 11 00 11 00 which is equal to 0x3BBEECC. Now with that magic number, all I needed to do was shift the right bits into the right position and OR them with 28.

function lookupBitwise(x) {
    return 28 | (0x3BBEECC >> x >> x) & 3;
}

That was better1 and it turned out to only take 20 bytes, smaller then my attempt at making a small version.

Results

Take a look at the jsPerf page to how they compare speed wise. Below is a compilation of all of the different functions I came up with:

 1 /**
 2  * Length of the Month  
 3  */
 4  
 5 var lotm = {
 6 
 7     lookupTable: [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31],
 8 
 9     curtisMcEnroe: function(x) {
10         return 28 + (x + Math.floor(x / 8)) % 2 + 2 % x + 2 * Math.floor(1 / x);
11     },
12 
13     bitwise: function(x) {
14         var y;
15         return (y = 30 | (x >> 3 ^ x) & 1) ^ (~(x >> 2 | x | y) & 1) << 1
16     },
17     
18     bitwiseEqual: function(x) {
19         return 28 | (x >> 3 ^ x) & 1 | (x !== 2) << 1; 
20     },
21 
22     lookup: function(x) {
23         return this.lookupTable[x];
24     },
25 
26     lookupBitwise: function(x) {
27         return 28 | (0x3BBEECC >> x >> x) & 3;
28     },
29 
30     bigSwitch: function(x) {
31         switch (x) {
32             case 1: return 31;
33             case 2: return 28;
34             case 3: return 31;
35             case 4: return 30;
36             case 5: return 31;
37             case 6: return 30;
38             case 7: return 31;
39             case 8: return 31;
40             case 9: return 30;
41             case 10: return 31;
42             case 11: return 30;
43             case 12: return 31;
44         }
45     },
46 
47     bigIf: function(x) {
48         if (x === 1) x = 31;
49         else if (x === 2) x = 28;
50         else if (x === 3) x = 31;
51         else if (x === 4) x = 30;
52         else if (x === 5) x = 31;
53         else if (x === 6) x = 30;
54         else if (x === 7) x = 31;
55         else if (x === 8) x = 31;
56         else if (x === 9) x = 30;
57         else if (x === 10) x = 31;
58         else if (x === 11) x = 30;
59         else if (x === 12) x = 31;
60         return x;
61     }
62 };
  1. Tested in Chrome 39.0.2171.71 32-bit on Windows 7 64-bit 2 3