Advanced Exercism • cpp

Leap

Challenge Overview

Determine whether a given year is a leap year.

Visit the leap exercise on Exercism to read the full instructions and download the exercise files.

Dig Deeper

Boolean chain

Chain of boolean expressions

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

The first boolean expression uses the remainder operator to check if the year is evenly divided by 4.

If the year is not evenly divisible by 4, then the chain will “short circuit” due to the next operator being a logical AND (&&), and will return false.
If the year is evenly divisible by 4, then the logical NOT operator is used to check if the year is not evenly divisible by 100.
If the year is not evenly divisible by 100, then the expression is true and the chain will “short-circuit” to return true, since the next operator is a logical OR (||).
If the year is evenly divisible by 100, then the expression is false, and the returned value from the chain will be if the year is evenly divisible by 400.

year	year % 4 == 0	year % 100 != 0	year % 400 == 0	is leap year
2020	true	true	not evaluated	true
2019	false	not evaluated	not evaluated	false
2000	true	false	true	true
1900	true	false	false	false

The chain of boolean expressions is efficient, as it proceeds from testing the most likely to least likely conditions. Howard Hinnant wrote a short paragraph about the order of operations on his web page about date-related algorithms.

Shortening

By using the implicit conversion from int to bool the code can be shortened using the logical NOT operator. Only 0 is converted to false and every non-zero value is converted to true.

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

Precedence

You may have noticed the parentheses around the boolean expressions above. Consider the following code:

bool many_parens    = ((year % 100) != 0) || ((year % 400) == 0);
bool some_parens    = (year % 100 != 0) || (year % 400 == 0);
bool no_parens      =  year % 100 != 0 || year % 400 == 0;

All lines produce the same result but differ a lot in readability. The reason for their equal results is the order of operator evaluation (%, !=, ||, etc) or precedence. In this example the first operator to get the attention of the compiler is the remainder, followed by the equality operators. Only then will the compiler go for && and then check ||. Mixing && and || at the same level of an expression is error-prone. Some people might overlook that and is evaluated before or and thus introduce bugs. This is a potential reason to keep some parenthesis, although they are not necessarily needed by the compiler. You might be able to follow the code like the compiler, but other developers might struggle.

true || false && true;
\\ => false
(true || false) && true;
\\ => true

Short-circuit evaluation

If a boolean expression’s value is not going to change with further evaluations, C++ code will short-circuit and skip these “unesssary” evaluations. They might not change the final result of the boolean, but side-effects will not take place.

bool print_and_always_false() {
    std::cout << "Hello!";
    return false;
}

bool print_and_always_true() {
    std::cout << "World!";
    return true;
}

print_and_always_false() && print_and_always_true();
// will only print "Hello!". `print_and_always_true`` is never called.

Short-circuiting is a way to speed up your programs by sorting your chain of booleans in a sensible order. One strategy might be to evaluate expensive operations late or very likely and unambiguous results first.

Ternary operator

bool is_leap_year(int year) {
    return year % 100 == 0 ? year % 400 == 0 : year % 4 == 0;
}

The conditional operator is also known as a “ternary conditional operator”, or just “ternary operator”. The implementation above uses a maximum of two checks to determine if a year is a leap year.

It starts by testing the outlier condition of the year being evenly divisible by 100. It does this by using the remainder operator. If the year is evenly divisible by 100, then the expression is true, and the ternary operator returns if the year is evenly divisible by 400. If the year is not evenly divisible by 100, then the expression is false, and the ternary operator returns if the year is evenly divisible by 4.

year	year % 100 == 0	year % 400 == 0	year % 4 == 0	is leap year
2020	false	not evaluated	true	true
2019	false	not evaluated	false	false
2000	true	true	not evaluated	true
1900	true	false	not evaluated	false

Although it uses a maximum of only two checks, the ternary operator tests an outlier condition first, making it less efficient than another approach that would first test if the year is evenly divisible by 4, which is more likely than the year being evenly divisible by 100.

Shortening

By using the implicit conversion from integer to bool the code can be shortened using the logical NOT operator. Only 0 is converted to false and every non-zero value is converted to true.

bool is_leap_year(int year) {
    return !(year % 100) ? !(year % 400) : !(year % 4);
}

It can be thought of as the expression not having a remainder.

Precedence

You may have noticed the braces around the boolean expressions above. Consider the following code:

bool many_braces    = ((year % 100) != 0) || ((year % 400) == 0);
bool some_braces    = (year % 100 != 0) || (year % 400 == 0);
bool no_braces      =  year % 100 != 0 || year % 400 == 0;

All lines produce the same result, but differ a lot in readability. The reason for their equal results, is the order of operator evaluation (%, !=, ||, etc) or precedence. In this example the first operator to get the attention of the compiler is the remainder, followed by the equality operators. Only then will the compiler go for && and then check ||. Some people might overlook that and is evaluated before or and thus introduce bugs. This is a potential reason to keep some braces, although they are not necessarily needed in the code.

true || false && true;
\\ => false
(true || false) && true;
\\ => true

Source: Exercism cpp/leap