使用位运算符进行闰年检查（惊人的速度）

Question

使用位运算符进行闰年检查（惊人的速度）

17

JSPerf上有人提供了一个非常快的ISO日历闰年检查实现（链接：Odd bit manipulations）：

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)
    );
}

它按预期工作，但我的问题是我无法理解如何实现。我知道当b是2的幂时((a%b)==(a&(b-1))，所以(year%4)==(year&3)，但year&15&& !(year%25) 很难理解。有人可以解释一下这是如何实现的吗？有关此实现的任何参考资料？

- Redger

2

只是出于好奇：优化后的用例究竟有什么用途？ - user123444555621

惊人的速度！如果你计划（重新）编写一个库，那就很有趣！ - Redger

好的...如果你必须在服务器端处理数十亿条包含日期的记录怎么办？Mark Ransom解释得非常好，所以我把他的答案放在了代码注释中，并给予了他的功劳和链接。我还在注释中包括了经典公式，但我使用了优化后的公式来完成工作。可读性没有被牺牲！事实上，我正在编写一个高度专业化的库，性能很重要。 - Redger

1

如果你有数十亿条记录并且性能很重要，那么你应该考虑使用一种不同的编程语言。 - user123444555621

1

我在这个问题上写了一个详细的答案...请参见https://dev59.com/hnA75IYBdhLWcg3wkaCA#11595914 - Kevin P. Rice

显示剩余2条评论

2个回答

5

如果一个数可以被16和25整除，那么它也可以被4倍的25（100）和16倍的25（400）整除。

- Pointy

那么如何进行能被400整除的检查呢？ - Gareth

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Ransom · Accepted Answer

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年不会是闰年。