判断闰年的算法 - C++ <chrono> 库

在 C++ <chrono> 库中，有如下判断闰年的算法：

class year
{
private:
    short _M_y;

public:
    constexpr bool
    is_leap() const noexcept
    {
        return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0;
    }
};

根据源代码的注释，总结一下优化思路：

判断闰年的规则是：

• 如果年份能被 4 整除且不能被 100 整除，则是闰年.
• 如果年份能被 100 整除，则还必须能被 400 整除，才是闰年.

先判断能否被 100 整除比其他思路更快，因为它减少了不必要的计算. 参考这里.

所以，逻辑优化成了：

return _M_y % 100 == 0 ? _M_y % 400 == 0 : _M_y % 4 == 0;

当知道一个数字能被 100 整除时，能被 400 整除实际上意味着它也可以被 16 整除.

标准库在第一步判断时没有使用 100 而是 25，因为检查被 25 整除的速度更快（汇编少了一句，参考这里），而且仍然管用.

因此，进一步优化为：

return _M_y % 25 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0;

• 如果一个数不能被 4 整除，那么它肯定也不能被 16 整除，所以在这种情况下，无论能否被 25 整除，都应该返回 false.

• 如果一个数能被 4 整除，那么它能被 25 整除当且仅当它能被 100 整除. 这是因为任何能被 25 整除的数都是以 00、25、50 或 75 结尾的，而只有以 00 结尾的数也能被 100 整除.

因此，优化前后的逻辑是等价的.

对于位运算：

• 如果年份 y 能被 25 整除，那么 y 的最后两位必须是 00、25、50 或 75，此时 y & 15 将检查 y 的最后四位是否都是 0，这等价于检查 y 能否被 100 整除.

• 如果年份 y 不能被 25 整除，那么 y & 3 将检查 y 的最后两位能否被 4 整除.

最终优化结果为：

bool
is_leap(int y)
{
    return (y & (y % 25 == 0 ? 15 : 3)) == 0;
}

你学会了吗.