闰年的最佳效率演算法

閏年的最佳效率演算法

所謂閏年，維基百科做了如是介紹：

閏年是比普通年分多出一段時間的年分，在各種曆法中都有出現，目的是為了彌補人為規定的紀年與地球公轉產生的差異。

目前使用的格里曆閏年規則如下：

  • 西元年分除以400可整除，為閏年。
  • 西元年分除以4可整除但除以100不可整除，為閏年。
  • 西元年分除以4不可整除，為平年。
  • 西元年分除以100可整除但除以400不可整除，為平年。

在C，C++，C#，Java，以及許多類C編程語言的入門書籍裏，舉凡講到運算子一節，一般都會提及閏年的演算法；且不出意外、一般皆為：

1
2
3
4

if (((year % 4) == 0 && (year % 100) != 0) || (year % 400) == 0)
{
    /* leap year */
}

這演算法簡單明瞭、但在效率上卻顯得差強人意；因而、在stackoverflow上有討論，認為若以效率考量、則最佳演算法為：

1
2
3
4

if ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0))
{
    /* leap year */
}

那麼、這「最佳效率」演算法如何得來呢？以下便是推演過程。

短路求值

有以下兩點：

  • 許多編程語言都有短路求值的策略
  • 不能被4整除的數、亦不能被400整除

則演算法可以重寫為：

1
2
3
4

if ((year % 4) == 0 && ((year % 100) != 0 || (year % 400) == 0))
{
    /* leap year */
}

這樣、舉凡不能被4整除的年份皆為平年（格里曆閏年規則#3）；不用再去運算(year % 400) == 0、大大提高了演算法的效率。

因式分解

因有等式100=4×25，則可被100整除等同於可被4和25整除。依據短路求值策略，在進行運算(year % 100) != 0時必有先決條件：運算式(year % 4) == 0為真，即年份可被4整除。

故而、演算法可以重寫為：

1
2
3
4

if ((year % 4) == 0 && ((year % 25) != 0 || (year % 400) == 0))
{
    /* leap year */
}

同理、因有400=25×16，演算法進一步可以重寫為：

1
2
3
4

if ((year % 4) == 0 && ((year % 25) != 0 || (year % 16) == 0))
{
    /* leap year */
}

位元與取代模除

執行模除運算需要除法。而除法運算在某些低端CPU上非常耗時。因而、最好避免不必要的模除運算。

特別地、當模數為2的指數冪時、模除運算可用位元與代替，即：x % 2^n == x & (2^n - 1)。

因而、演算法可以重寫為：

if ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0))
{
    /* leap year */
}

至此、推演告一段落；不過、以下兩點更加有趣哦～

15還是12

有以下三點：

運算式(year & 3) == 0檢查年份的[0..1]位元是否皆為0 運算式(year & 12) == 0檢查年份的[2..3]位元是否皆為0 運算式(year & 15) == 0檢查年份的[0..3]位元是否皆為0 因而、#3可由#1與#2協同完成；而依據短路求值策略，在進行運算(year & 15) == 0時必有先決條件：運算式(year & 3) == 0為真。

故15也可以12替代、演算法也可重寫為：

1
2
3
4

if ((year & 3) == 0 && ((year % 25) != 0 || (year & 12) == 0))
{
    /* leap year */
}

4000年問題

按照現行閏年規則，西元4000年應當為閏年；但到西元8000時，時日又會有所差錯，故有提議西元4000年為平年，並修改規則為：

西元年分除以4000可整除，為平年。 西元年分除以400可整除但除以4000不可整除，為閏年。 西元年分除以4可整除但除以100不可整除，為閏年。 西元年分除以4不可整除，為平年。 西元年分除以100可整除但除以400不可整除，為平年。 據此、又有人提出了「最終極」「最佳效率」演算法：

1
2
3
4

if ((year & 3) == 0 && ((year % 25) != 0 || ((year & 15) == 0 && (year % 4000) != 0)))
{
    /* leap year */
}

其他语言写法

1
2
3
4
5
6


def leap_year(year):
    if year & 3 == 0 and (year % 25 != 0 or year & 15 == 0):
        return True
    else:
        return False