Skip to main content

Leap year check using bitwise operators (amazing speed)


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: Tips4allCCNA FINAL EXAM

Comments

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

    ReplyDelete
  2. 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

Post a Comment

Popular posts from this blog

Why is this Javascript much *slower* than its jQuery equivalent?

I have a HTML list of about 500 items and a "filter" box above it. I started by using jQuery to filter the list when I typed a letter (timing code added later): $('#filter').keyup( function() { var jqStart = (new Date).getTime(); var search = $(this).val().toLowerCase(); var $list = $('ul.ablist > li'); $list.each( function() { if ( $(this).text().toLowerCase().indexOf(search) === -1 ) $(this).hide(); else $(this).show(); } ); console.log('Time: ' + ((new Date).getTime() - jqStart)); } ); However, there was a couple of seconds delay after typing each letter (particularly the first letter). So I thought it may be slightly quicker if I used plain Javascript (I read recently that jQuery's each function is particularly slow). Here's my JS equivalent: document.getElementById('filter').addEventListener( 'keyup', function () { var jsStart = (new Date).getTime()...

Is it possible to have IF statement in an Echo statement in PHP

Thanks in advance. I did look at the other questions/answers that were similar and didn't find exactly what I was looking for. I'm trying to do this, am I on the right path? echo " <div id='tabs-".$match."'> <textarea id='".$match."' name='".$match."'>". if ($COLUMN_NAME === $match) { echo $FIELD_WITH_COLUMN_NAME; } else { } ."</textarea> <script type='text/javascript'> CKEDITOR.replace( '".$match."' ); </script> </div>"; I am getting the following error message in the browser: Parse error: syntax error, unexpected T_IF Please let me know if this is the right way to go about nesting an IF statement inside an echo. Thank you.