使用按位运算符进行闰年检查(惊人的速度)

Question

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 && !(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)
    );
}

它按预期工作,但我的问题是我无法弄清楚如何.我知道((a % b) == (a & (b-1))当b是2的幂时(year % 4) == (year & 3),但year & 15 && !(year % 25)很难弄明白.谁能解释一下它是如何工作的？有关此实现的任何参考？

Answer 1

year & 3是一样的year % 4.在那里并不那么棘手,它只是代表了通常的4年周期.

year & 15是一样的year % 16.

因此,它是不是闰年,如果一年不被4整除,或者如果它不被16整除但由25整除这意味着,每25多个是不是闰年,除非它也是16.由于16和25没有任何共同因素,因此只有当年份是16*25或400年的倍数时才能满足这两个条件.4*25的倍数将被视为闰年,占100年周期.

1900年不是闰年,因为它可以被100整除,2000 年是闰年,因为它可以被400整除,2100年不会是闰年.

Answer 2

如果一个数字可被16整除并可被25整除,则它可被25整除(16)和16乘25(400)四倍.