如何在C中以编程方式查找闰年

Question

我使用C制作了一个程序来查找输入的年份是否是闰年.但遗憾的是它运作不佳.它说一年是飞跃,前一年不是飞跃.

#include<stdio.h>
#include<conio.h>
int yearr(int year);
void main(void)
{
    int year;
    printf("Enter a year:");
    scanf("%d",&year);
    if(!yearr(year))
    {
        printf("It is a leap year.");
    }
    else
    {
    printf("It is not a leap year");
    }


getch();
}
int yearr(int year)
{
    if((year%4==0)&&(year/4!=0))
    return 1;
    else
    return 0;
}

阅读评论后,我编辑了我的编码:

#include<stdio.h>
#include<conio.h>
int yearr(int year);
void main(void)
{
    int year;
    printf("Enter a year:");
    scanf("%d",&year);
    if(!yearr(year))
    {
        printf("It is a leap year.");
    }
    else
    {
    printf("It is not a leap year");
    }


getch();
}
int yearr(int year)
{
    if((year%4==0)
    {
    if(year%400==0)
    return 1;
    if(year%100==0)
    return 0; 
    }
    else
    return 0;
}

Answer 1

最有效的闰年测试:

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

此代码在C,C++,C#,Java和许多其他类C语言中有效.该代码使用单个TRUE/FALSE表达式,该表达式由三个单独的测试组成:

• 第四年测试: year & 3
• 第100年测试: year % 25
• 第400年测试: year & 15

有关此代码如何工作的完整讨论如下所示,但首先需要讨论维基百科的算法:

维基百科算法是不充分/不可靠的

维基百科发布了一种伪代码算法(参见:维基百科:闰年 - 算法),该算法经常受到编辑,舆论和故意破坏.

不要实施WIKIPEDIA算法!

最长期(且效率低下)的维基百科算法之一如下:

if year modulo 400 is 0 then
   is_leap_year
else if year modulo 100 is 0 then
   not_leap_year
else if year modulo 4 is 0 then
   is_leap_year
else
   not_leap_year

上述算法是低效的,因为它总是执行400年和100年的测试,即使是很快就会失败的"第4年测试"(模4测试) - 这是75%的时间!通过重新排序算法来执行第4年测试,我们首先加快了速度.

"最有效"的伪代码算法

我向维基百科提供了以下算法(不止一次):

if year is not divisible by 4 then not leap year
else if year is not divisible by 100 then leap year
else if year is divisible by 400 then leap year
else not leap year

这种"最有效"的伪代码只是改变了测试的顺序,因此首先进行4除法,然后进行频率较低的测试.因为"年份"不会分成四个75%的时间,所以算法在四个案例中的三个案例中仅进行一次测试后结束.

注意:我已经与各种维基百科编辑进行了斗争,以改进在那里发布的算法,认为许多新手和专业程序员很快到达维基百科页面(由于顶级搜索引擎列表)并实施维基百科伪代码而无需进一步研究.维基百科编辑拒绝并删除了我为改进,注释甚至仅仅注释已发布的算法所做的每一次尝试.显然,他们觉得找到效率是程序员的问题.这可能是真的,但许多程序员都急于进行扎实的研究!

讨论"最有效"的年度试验

按位-AND代替模数:

我已经使用按位AND运算替换了维基百科算法中的两个模运算.为什么以及如何？

执行模数计算需要除法.在编程PC时,人们通常不会三思而后行,但是当编程嵌入在小型设备中的8位微控制器时,您可能会发现CPU无法原生执行除法功能.在这样的CPU上,除法是一个艰难的过程,涉及重复循环,位移和加/减操作,这些操作非常慢.非常希望避免.

事实证明,使用按位AND运算可以交替地实现两个幂的模数(参见:Wikipedia:Modulo operation - Performance Issues):

x%2 ^ n == x&(2 ^ n - 1)

许多优化编译器会将这些模运算转换为按位AND,但对于较小和较不流行的CPU,不太先进的编译器可能不会.Bitwise-AND是每个CPU上的单个指令.

通过使用和替换modulo 4和modulo 400测试(参见下文:'Factoring to reduce math'),我们可以确保在不使用更慢的除法运算的情况下获得最快的代码.& 3& 15

没有两个等于100的幂.因此,我们被迫继续使用模运算进行100年测试,但是100被替换为25(见下文).

考虑简化数学:

除了使用按位AND替换模运算之外,您还可以注意到维基百科算法和优化表达式之间的另外两个争议:

• modulo 100 被替换为 modulo 25
• modulo 400 被替换为 & 15

第100次测试使用modulo 25而不是modulo 100.我们可以做到这一点,因为100个因子超出2 x 2 x 5 x 5.因为第4年的测试已经检查了因子4,我们可以从100中消除该因子,留下25个.这种优化对于几乎每个CPU实现都可能是微不足道的(因为100和25都适合8位).

第400年的测试使用& 15相当于modulo 16.同样,我们可以做到这一点,因为有400个因子可以达到2 x 2 x 2 x 2 x 5 x 5.我们可以消除因为第100次测试而测试的因子25,留下16个.我们不能进一步减少16因为8是因此,消除任何更多的因素将导致200年不需要的积极因素.

对于8位CPU来说,第400年的优化非常重要,首先是因为它避免了划分; 但更重要的是,因为值400是9位数,在8位CPU中处理起来要困难得多.

短路逻辑AND/OR运算符:

使用的最后也是最重要的优化是短路逻辑AND('&&')和OR('||')运算符(参见:维基百科:短路评估),它们以大多数类C语言实现.短路操作符之所以如此命名,是因为如果左侧的表达式本身决定了操作的结果,那么它们就不会费心去评估右侧的表达式.

例如:如果年份是2003年,year & 3 == 0则为假.逻辑AND右侧的测试无法使结果成立,因此无法评估任何其他内容.

通过首先执行第四年测试,仅四分之三(75%)的时间评估第四年测试(简单的按位-AND).这大大加快了程序的执行速度,特别是因为它避免了第100年测试所需的划分(模25操作).

关于父母安置的说明

一位评论者认为括号在我的代码中放错位置,并建议子表达式在逻辑AND运算符(而不是逻辑OR)周围重新分组,如下所示:

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

以上是不正确的.逻辑AND运算符的优先级高于逻辑OR,并且首先使用或不使用新括号进行求值.逻辑AND参数周围的括号无效.这可能导致人们完全消除子分组:

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

但是,在上述两种情况下,逻辑OR(第400年测试)的右侧几乎每次都被评估(即,不能被4和100整除的年份).因此,错误地消除了有用的优化.

我原始代码中的括号实现了最优化的解决方案:

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

这里,逻辑OR仅被评估为可被4整除的年份(因为短路AND).逻辑OR的右侧仅评估可被4和100整除的年份(因为短路OR).

C/C++程序员注意事项

C/C++程序员可能会觉得这个表达式更加优化:

if (!(year & 3) && ((year % 25) || !(year & 15))) { /* LY */ }

这不是更优化!虽然显式== 0和!= 0测试被删除,但它们变得隐含并且仍然执行.更糟糕的是,代码在强类型语言中不再有效,例如C#,其中year & 3求值为a int,但逻辑AND(&&),OR(||)和NOT(!)运算符需要bool参数.

Answer 2

你确定闰年的逻辑是错误的.这应该让你开始(来自维基百科):

if year modulo 400 is 0
       then is_leap_year
else if year modulo 100 is 0
       then not_leap_year
else if year modulo 4 is 0
       then is_leap_year
else
       not_leap_year

x modulo y是指剩下的x除以y.例如,12模5是2.

Answer 3

许多答案谈论性能。无显示任何测量。来自 gcc 文档的一个很好的引用是这样__builtin_expect说的：

众所周知，程序员不擅长预测他们的程序实际执行情况。

大多数实现使用&&和||作为优化工具的短路，并继续为“最佳”性能的可分性检查规定“正确”的顺序。值得一提的是，短路不一定是优化功能。

同意，某些检查可能会给出明确的答案（例如，年份不是 4 的倍数）并使后续测试无用。在这一点上立即返回而不是继续进行不必要的计算似乎是合理的。另一方面，早期返回会引入分支，这可能会降低性能。（请参阅这篇传奇文章。）很难猜测分支预测错误和不必要的计算之间的权衡。实际上，它取决于硬件、输入数据、编译器发出的确切汇编指令（可能会从一个版本更改为另一个版本）等。

续集应显示在quick-bench.com 中获得的测量结果。在所有情况下，我们都会测量检查存储在std::array<int, 65536>a中的每个值是否为闰年所花费的时间。这些值是伪随机的，均匀分布在区间 [-400, 399] 中。更准确地说，它们是由以下代码生成的：

auto const years = [](){
  std::uniform_int_distribution<int> uniform_dist(-400, 399);
  std::mt19937 rng;
  std::array<int, 65536> years;
  for (auto& year : years)
    year = uniform_dist(rng);
  return years;
}();

即使可能，我也不会替换%为&（例如year & 3 == 0代替year % 4 == 0）。我相信编译器（GCC-9.2 at -O3）会为我做到这一点。（确实如此。）

4-100-400 次测试

闰年的检查通常根据三个可分性测试编写：year % 4 == 0、year % 100 != 0和year % 400 == 0。以下是涵盖所有可能出现这些检查的顺序的实现列表。每个实现都以相应的标签为前缀。（有些命令允许两种不同的实现，在这种情况下，第二个得到后缀b。）它们是：

b4_100_400  : year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
b4_100_400b : (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
b4_400_100  : year % 4 == 0 && (year % 400 == 0 || year % 100 != 0)
b100_4_400  : (year % 100 != 0 && year % 4 == 0) || year % 400 == 0
b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0
b400_4_100  : year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)
b400_100_4  : year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)
b400_100_4b : (year % 400 == 0 || year % 100 != 0) && year % 4 == 0

结果如下所示。（现场观看。）

与许多人的建议相反，4首先检查可分性似乎不是最好的做法。相反，至少在这些测量中，前三个柱是最差的五个。最好的是

b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0

4-25-16 测试

另一个提供尖端（我必须承认我认为是一个很好的）被替换year % 100 != 0用year % 25 != 0。这不会影响正确性，因为我们还会检查year % 4 == 0. （如果一个数是 的倍数，则被4整除100等于 被 整除25。）同样，由于存在可整除性检查，year % 400 == 0可以替换year % 16 == 0为25。

和上一节一样，我们有 8 个使用 4-25-16 可分性检查的实现：

b4_25_16  : year % 4 == 0 && (year % 25 != 0 || year % 16 == 0)
b4_25_16b : (year % 4 == 0 && year % 25 != 0) || year % 16 == 0
b4_16_25  : year % 4 == 0 && (year % 16 == 0 || year % 25 != 0)
b25_4_16  : (year % 25 != 0 && year % 4 == 0) || year % 16 == 0
b25_16_4  : (year % 25 != 0 || year % 16 == 0) && year % 4 == 0
b16_4_25  : year % 16 == 0 || (year % 4 == 0 && year % 25 != 0)
b16_25_4  : year % 16 == 0 || (year % 25 != 0 && year % 4 == 0)
b16_25_4b : (year % 16 == 0 || year % 25 != 0) && year % 4 == 0

结果（住在这里）：

同样，4首先检查可分性看起来不是一个好主意。在这一轮中，斋戒是

b25_16_4  : (year % 25 != 0 || year % 16 == 0) && year % 4 == 0

4-100-400 次测试（无分支）

如前所述，分支可能会降低性能。特别是，短路可能会适得其反。在这种情况下，一个经典的诀窍是代替逻辑运算符&&，并||与他们的逐位同行&和|。实现变为：

nb4_100_400  : (year % 4 == 0) & ((year % 100 != 0) | (year % 400 == 0))
nb4_100_400b : ((year % 4 == 0) & (year % 100 != 0)) | (year % 400 == 0)
nb4_400_100  : (year % 4 == 0) & ((year % 400 == 0) | (year % 100 != 0))
nb100_4_400  : ((year % 100 != 0) & (year % 4 == 0)) | (year % 400 == 0)
nb100_400_4  : ((year % 100 != 0) | (year % 400 == 0)) & (year % 4 == 0)
nb400_4_100  : (year % 400 == 0) | ((year % 4 == 0) & (year % 100 != 0))
nb400_100_4  : (year % 400 == 0) | ((year % 100 != 0) & (year % 4 == 0))
nb400_100_4b : ((year % 400 == 0) | (year % 100 != 0)) & (year % 4 == 0)

结果（住在这里）：

一个值得注意的特点是性能变化不像分支情况那样明显，并且很难宣布获胜者。我们选择这个：

nb100_400_4  : ((year % 100 != 0) | (year % 400 == 0)) & (year % 4 == 0)

4-25-16 测试（无分支）

为了完成练习，我们考虑具有 4-25-16 可分性测试的无分支情况：

nb4_25_16  : (year % 4 == 0) & ((year % 25 != 0) | (year % 16 == 0))
nb4_25_16b : ((year % 4 == 0) & (year % 25 != 0)) | (year % 16 == 0)
nb4_16_25  : (year % 4 == 0) & ((year % 16 == 0) | (year % 25 != 0))
nb25_4_16  : ((year % 25 != 0) & (year % 4 == 0)) | (year % 16 == 0)
nb25_16_4  : ((year % 25 != 0) | (year % 16 == 0)) & (year % 4 == 0)
nb16_4_25  : (year % 16 == 0) | ((year % 4 == 0) & (year % 25 != 0))
nb16_25_4  : (year % 16 == 0) | ((year % 25 != 0) & (year % 4 == 0))
nb16_25_4b : ((year % 16 == 0) | (year % 25 != 0)) & (year % 4 == 0)

结果（住在这里）：

再一次，很难定义最好的，我们选择了这个：

nb25_16_4  : ((year % 25 != 0) | (year % 16 == 0)) & (year % 4 == 0)

冠军联赛

现在是时候选择前面每个部分中最好的部分并进行比较：

b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0
b25_16_4    : (year % 25 != 0 || year % 16 == 0) && year % 4 == 0
nb100_400_4 : ((year % 100 != 0) | (year % 400 == 0)) & (year % 4 == 0)
nb25_16_4   : ((year % 25 != 0) | (year % 16 == 0)) & (year % 4 == 0)

结果（住在这里）：

该图表表明短路确实是一种优化，但4应最后检查而不是第一个检查可整除性。为了获得更好的性能，100首先应该检查可分性。这相当令人惊讶！毕竟，后一个测试永远不足以确定年份是否为闰年，并且始终需要后续测试（by400或 by 4）。

同样令人惊讶的是，对于使用更简单除数的分支版本25，16并不比使用更直观的100和400. 我可以提供我的“理论”，这也部分解释了为什么测试100first 比测试4. 正如许多人指出的那样，可分性测试4将执行分成 (25%, 75%) 部分，而测试100将其分成 (1%, 99%)。在后一个检查之后，执行必须继续进行另一个测试并不重要，因为至少，分支预测器更有可能正确猜测要走哪条路。类似地，通过以下方式检查可除性25将执行分成 (4%, 96%)，这对分支预测器来说比 (1%, 99%) 更具挑战性。看起来最好是最小化分布的熵，帮助分支预测器，而不是最大化早期返回的概率。

对于无分支版本，简化的除数确实提供了更好的性能。在这种情况下，分支预测器不起作用，因此越简单越好。通常，编译器可以使用较小的数字执行更好的优化。

是这个吗？

我们是不是撞墙了才发现

b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0

是最高效的闰年检查吗？当然不。例如，我们没有混合分支运算符&&或||没有分支运算符&和|。也许......让我们看看上面的内容并将其与其他两个实现进行比较。第一个是

m100_400_4 : (year % 100 != 0 || year % 400 == 0) & (year % 4 == 0)

（注意分支||和非分支&运算符的混合。）第二个是一个晦涩的“黑客”：

bool b;
auto n = 0xc28f5c29 * year;
auto m = n + 0x051eb850;
m = (m << 30 | m >> 2);
if (m <= 0x28f5c28)
  b = n % 16 == 0;
else
  b = n % 4 == 0;
return b

后者有效吗？是的，它确实。我建议将上面发出的代码与这个更具可读性的源代码进行比较，而不是给出数学证明：

bool b;
if (year % 100 == 0)
  b = year % 16 == 0;
else
  b = year % 4 == 0;
return b;

在编译器资源管理器中。它们几乎相同，唯一的区别是一个使用add指令而另一个使用lea. 这应该使您相信黑客代码确实有效（只要其他人有效）。

基准测试结果（住在这里）：

等等，我听到你说，为什么不使用上图中更具可读性的代码？好吧，我已经尝试并学到了另一课。当这段代码被插入到基准测试循环中时，编译器会从整体上查看源代码，并决定发出与单独查看源代码时不同的代码。表现更差。去搞清楚！

现在？是这个吗？

我不知道！我们可以探索的东西很多。例如，最后一节展示了另一个使用if语句而不是短路的版本。这可能是获得更好性能的一种方式。我们也可以试试三元运算符?。

请注意，所有测量和结论均基于 GCC-9.2。使用另一个编译器和/或版本，事情可能会改变。例如，9.1 版的 GCC 引入了一种新的改进算法，用于可分性检查。因此，旧版本具有不同的性能，并且不必要的计算和分支错误预测之间的权衡可能已经改变。

我们可以肯定地得出以下几点：

1. 别想太多。更喜欢清晰的代码而不是难以理解的优化（除非你是一个库编写者，为你的用户围绕非常有效的实现提供更高级别的 API）。毕竟，当您升级编译器时，手工制作的代码段可能不是性能最高的选项。正如ex-nihilo在评论中所说，“除非已知它是性能瓶颈，否则对这样的一段代码大惊小怪是没有意义的。”
2. 猜测是困难的，最好是衡量。
3. 测量很难，但总比猜测好。
4. 短路/分支对性能有好处，但它取决于许多因素，包括代码对分支预测器的帮助程度。
5. 单独为代码片段发出的代码在某处内联时可能会有所不同。

Answer 4

int isLeapYear(int year)
{
   return (year % 400 == 0) || ( ( year % 100 != 0) && (year % 4 == 0 ));
}