Leap year check using bitwise operators (amazing speed)

Question

Someone on JSPerf dropped an amazingly fast implementation for checking leap years of the ISO calendar (link: Odd bit manipulations):

function isLeapYear(year) {
  return !(year & 3 || year & 15 && !(year % 25));
}

Using Node.js, I quickly checked it against two other one-liner implementations I know.

function isLeapClassic(y) { return (y % 4 == 0) && !(y % 100 == 0) || (y % 400 == 0); }
function isLeapXOR(y) { return (y % 4 == 0) ^ (y % 100 == 0) ^ (y % 400 == 0); }
function isLeapBitwise(y) { return !(y & 3 || y & 15 && !(y % 25)); }

//quick'n'dirty test on a small range!
//works with negative integers too
for (var i = 1900; i <= 2100; i++) {
    console.log(
        "year = %d,\t%d%d%d",
        i,
        isLeapClassic(i),
        isLeapXOR(i),
        isLeapBitwise(i)
    );
}

It works as expected, but my problem is I can't figure how. I know ((a % b) == (a & (b-1)) when b is power of two so (year % 4) == (year & 3), but year & 15 && !(year % 25) is quite hard to figure out. Can someone explain me how it works? Any reference about this implementation?

Just out of curiosity: What exactly is the usecase for having that optimized? — user123444555621, Mar 25 '12 at 12:34
The amazing speed! It's interesting if you plan to (re)write a library of course! — Redger, Mar 25 '12 at 12:54
I would never sacrifice readibility for a performance gain of a nanosecond. — user123444555621, Mar 25 '12 at 13:17
Well... what if you have to deal with billions of records containing dates on the server side? Mark Ransom explained it very well so I put his answer and giving him credits and link inside the comments in the code. I also include the classic formula in the comments but I use the optimized one to get the job done. Readibility is not sacrified! In fact I'm writing a highly specialized library and performance matters. — Redger, Mar 25 '12 at 13:44
If you have billions of records and performance matters you should consider using a different language. — user123444555621, Mar 25 '12 at 13:48
I agree because Javascript is not my first choice as a language but we are using Node.js and I'm not planning to write a custom C++ extension for V8... :-( — Redger, Mar 25 '12 at 14:08
I wrote a detailed answer on this... See http://stackoverflow.com/a/11595914/733805 — Kevin P. Rice, Jan 30 '13 at 10:26

score 14 · Accepted Answer · answered Mar 24 '12 at 15:40

year & 3 is the same as year % 4. Not so tricky there, it just represents the usual 4-year cycle.

year & 15 is the same as year % 16.

So, it's not a leap year if the year doesn't divide evenly by 4, or if it doesn't divide evenly by 16 but does divide evenly by 25. This means that every multiple of 25 is not a leap year unless it's also a multiple of 16. Since 16 and 25 don't have any common factors, the only time both conditions are met is when the year is a multiple of 16*25, or 400 years. The multiples of 4*25 will be considered not leap years, accounting for the 100 year cycle.

1900 wasn't a leap year because it was divisible by 100, 2000 was a leap year because it was divisible by 400, and 2100 won't be a leap year.

Your detailed explanation lead to me use this algorithm into my day-in-month code http://stackoverflow.com/questions/1810984/number-of-days-in-any-month/27946635#27946635 (basically I won't use code in a solution unless I understand it completely). Thanks and +1 for the great detail :) — iCollect.it Ltd, Jan 16 '15 at 15:28

score 5 · Answer 2 · answered Mar 24 '12 at 15:21

5

If a number is divisible by 16 and divisible by 25, it's divisible by four times 25 (100) as well as 16 times 25 (400).

answered Mar 24 '12 at 15:21

Pointy

405,095
59
585
614

So how does that do the divisible by 400 check? – Gareth Mar 24 '12 at 15:24

Leap year check using bitwise operators (amazing speed)

2 Answers2

Linked