Leap Year Test in K&R
About 18 years ago, while learning to program a computer using C, I learnt the following test for leap year from the book The C Programming Language, 2nd ed. (K&R) written by Brian Kernighan and Dennis Ritchie. Section 2.5 (Arithmetic Operators) of the book uses the following test:
(year % 4 == 0 && year % 100 != 0) || year % 400 == 0
It came as a surprise to me. Prior to reading this, I did not know that centurial years are not leap years except for those centurial years that are also divisible by 400. Until then, I always incorrectly thought that all years divisible by 4 are leap years. I have witnessed only one centurial year, namely the year 2000, which happens to be divisible by 400. As a result, the year 2000 proved to be a leap year and my misconception remained unchallenged for another few years until I finally came across the above test in K&R.
Now that I understand that centurial years are not leap years unless
divisible by 400, it is easy to confirm this with the
Unix cal command. Enter cal 1800
or cal 1900 and we see calendars of non-leap years.
But enter cal 2000 and we see the calendar of a leap
year.
By the way, the following leap year test is equally effective:
year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
Update: In the
comments section,
Thaumasiotes explains why both tests work. Let me take the liberty
of elaborating that comment further with a truth table. We use the
notation A, B, and C,
respectively, for the three comparisons in the above expressions.
Then the two tests above can be expressed as the following boolean expressions:
(A && B) || CA && (B || C)
Now normally these two boolean expressions are not equivalent. The truth table below shows this:
A |
B |
C |
(A && B) || C |
A && (B || C) |
|---|---|---|---|---|
| F | F | F | F | F |
| F | F | T | T | F |
| F | T | F | F | F |
| F | T | T | T | F |
| T | F | F | F | F |
| T | F | T | T | T |
| T | T | F | T | T |
| T | T | T | T | T |
We see that there are two cases where the last two columns differ.
Therefore indeed the two boolean expressions are not equivalent.
The two cases where the boolean expressions yield different results
occur when A is false and C is true. But
these cases are impossible! If A is false
and C is true, it means we have year % 4 !=
0 and year % 400 == 0 which is impossible.
If year % 400 == 0 is true, then year % 4 ==
0 must also hold true. In other words, if C is
true, A must also be true. Therefore, the two cases
where the last two columns differ cannot occur and may be ignored.
The last two columns are equal in all other cases and that is why
the two tests we have are equivalent.