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?
Source: Tips4all
year & 3 is the same as year % 4. Not so tricky there, it just represents the usual 4-year cycle.
ReplyDeleteyear & 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.
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).
ReplyDelete