闰年检查使用按位运算符（惊人的速度） [英] Leap year check using bitwise operators (amazing speed)

问题描述

JSPerf上的某人下载了一个惊人的快速实施，用于检查ISO日历的闰年（链接：奇数位操作）：

  function isLeapYear（year）{
 return！（year& 3 || year& 15 &&！（year％25））; 
} 
  

使用Node.js，我快速检查了另外两个单线程实现我知道。

  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&&！ } 
 
 //在一个小范围内quick'n'dirty测试！ 
 //与负整数一起使用
 for（var i = 1900; i <= 2100; i ++）{
 console.log（
year =％d， \\ t％d％d％d，
i，
 isLeapClassic（i），
 isLeapXOR（i），
 isLeapBitwise（i）
）; 
} 
  

它按预期工作，但我的问题是我不能说明如何。
当b是2的幂时，我知道（（a％b）==（a&（b-1）） （年％4）==（年& 3），但年&&很难找出，有人可以解释一下它的工作原理吗？任何关于这个实现的参考？

解决方案

year& 3 与 year％4 相同，不是那么棘手，只是代表通常的4年周期。 p>



年份& 15 与年份％16相同 。

因此，如果年份不均匀地除以4，或者如果它不均匀分布，则不是 16，但是除以25均匀。这意味着25的每个倍数不是闰年，除非它也是16的倍数。由于16和25没有任何公共因子，所以满足两个条件的唯一时间是当年是16 * 25或400年的倍数，4 * 25的倍数将被认为不是闰年，占100年周期。

1900年闰年，因为它可以被100，2000分割是闰年，因为它可以被400整除，2100不会是闰年。

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?

解决方案

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.

这篇关于闰年检查使用按位运算符（惊人的速度）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！