In C++, why does true && true || false && false == true?

Question

I'd like to know if someone knows the way a compiler would interpret the following code:

#include <iostream>
using namespace std;

int main() {
 cout << (true && true || false && false) << endl; // true
}

Is this true because && has a higher precedence than || or because || is a short-circuit operator (in other words, does a short circuit operator disregard all subsequent expressions, or just the next expression)?

Solution 1

Caladain has exactly the right answer, but I wanted to respond to one of your comments on his answer:

If short-circuiting the || operator occurs and short-circuits the execution of the second && expression, that means the || operator was executed BEFORE the second && operator. This implies left-to-right execution for && and || (not && precedence).

I think part of the problem you're having is that precedence doesn't quite mean what you think it means. It is true that && has higher precedence than ||, and this exactly accounts for the behavior you're seeing. Consider the case with ordinary arithmetic operators: suppose we have a * b + c * (d + e). What precedence tells us is how to insert parentheses: first around *, then around +. This gives us (a * b) + (c * (d + e)); in your case, we have (1 && 1) || (infiniteLoop() && infiniteLoop()). Then, imagine the expressions becoming trees. To do this, transform each operator into a node with its two arguments as children:

Evaluating this tree is where short-circuiting comes in. In the arithmetic tree, you can imagine a breadth-first bottom-up execution style: first evaluate DE = d + e, then AB = a * b and CDE = c * DE, and the final result is AB + CDE. But note that you could equally well have evaluated AB first, then DE, CDE, and the final result; you can't tell the difference. However, since || and && are short-circuiting, they have to use this leftmost-first evaluation. Thus, to evaluate the ||, we first evaluate 1 && 1. Since this is true, || short-circuits and ignores its right-hand branch—even though, if it had evaluated it, it would have had to evaluate the infiniteLoop() && infiniteLoop() first.

If it helps, you can think of each node in the tree as a function call, which produces the following representation plus(times(a,b), times(c,plus(d,e))) in the first case, and or(and(1,1), and(infiniteLoop(),infiniteLoop()) in the second case. Short-circuiting means that you have to fully evaluate each left-hand function argument to or or and; if it's true (for or) or false (for and), then ignore the right-hand argument.

Your comment presupposes that we evaluate everything with highest precedence first, then everything with next-highest precedence, and so on and so forth, which corresponds to a breadth-first bottom-up execution of the tree. Instead, what happens is that precedence tells us how to build the tree. The rules for execution of the tree are irrelevant in the simple arithmetic case; short-circuiting, however, is precisely an exact specification of how to evaluate the tree.

---

Edit 1: In one of your other comments, you said

Your arithmetic example necessitates the two multiplications to be evaluated before the final addition, is that not what defines precedence?

Yes, this is what defines precedence—except it's not quite true. It's certainly exactly true in C, but consider how you would evaluate the (non-C!) expression 0 * 5 ^ 7 in your head, where 5 ^ 7 = 57 and ^ has higher precedence than *. According to your breadth-first bottom-up rule, we need to evaluate 0 and 5 ^ 7 before we can find the result. But you wouldn't bother to evaluate 5 ^ 7; you'd just say "well, since 0 * x = 0 for all x, this must be 0", and skip the whole right-hand branch. In other words, I haven't evaluated both sides fully before evaluating the final multiplication; I've short-circuited. Similarly, since false && _ == false and true || _ == true for any _, we may not need to touch the right-hand side; this is what it means for an operator to be short-circuiting. C doesn't short-circuit multiplication (although a language could do this), but it does short-circuit && and ||.

Just as short-circuiting 0 * 5 ^ 7 doesn't change the usual PEMDAS precedence rules, short-circuiting the logical operators doesn't change the fact that && has higher precedence than ||. It's simply a shortcut. Since we have to choose some side of the operator to evaluate first, C promises to evaluate the left-hand side of the logical operators first; once it's done this, there's an obvious (and useful) way to avoid evaluating the right-hand side for certain values, and C promises to do this.

Your rule—evaluate the expression breadth-first bottom-up—is also well-defined, and a language could choose to do this. However, it has the disadvantage of not permitting short-circuiting, which is a useful behavior. But if every expression in your tree is well-defined (no loops) and pure (no modifying variables, printing, etc.), then you can't tell the difference. It's only in these strange cases, which the mathematical definitions of "and" and "or" don't cover, that short-circuiting is even visible.

Also, note that there's nothing fundamental about the fact that short-circuiting works by prioritizing the leftmost expression. One could define a language Ɔ, where ⅋⅋ represents and and \\ represents ||, but where 0 ⅋⅋ infiniteLoop() and 1 \\ infiniteLoop() would loop, and infiniteLoop() ⅋⅋ 0 and infiniteLoop() \\ 1 would be false and true, respectively. This just corresponds to choosing to evaluate the right-hand side first instead of the left-hand side, and then simplifying in the same way.

In a nutshell: what precedence tells us is how to build the parse tree. The only sensible orders for evaluating the parse tree are those that behave as if we evaluate it breadth-first bottom-up (as you want to do) on well-defined pure values. For undefined or impure values, some linear order must be chosen.¹ Once a linear order is chosen, certain values for one side of an operator may uniquely determine the result of the whole expression (e.g., 0 * _ == _ * 0 == 0, false && _ == _ && false == false, or true || _ == _ || true == true). Because of this, you may be able to get away without completing the evaluation of whatever comes afterwards in the linear order; C promises to do this for the logical operators && and || by evaluating them in a left-to-right fashion, and not to do it for anything else. However, thanks to precedence, we do know that true || true && false is true and not false: because

  true || true && false
→ true || (true && false)
→ true || false
→ true

instead of

  true || true && false
↛ (true || true) && false
→ true && false
→ false

---

1: Actually, we could also theoretically evaluate both sides of an operator in parallel, but that's not important right now, and certainly wouldn't make sense for C. This gives rise to more flexible semantics, but one which has problems with side-effects (when do they happen?).

Solution 2

&& has a higher precedence than ||.

Solution 3

(true && true || false && false) is evaluated with && having higher precedence.

TRUE && TRUE = True

FALSE && FALSE = False

True || False = True

Update:

1&&1||infiniteLoop()&&infiniteLoop()

Why does this produce true in C++?

Like before, lets break it apart. && has higher precedence that || and boolean statements short circuit in C++.

1 && 1 = True.

When a bool value is converted to an integer value, then

false -> 0
true -> 1

The expression evaluates this (true) && (true) statement, which short circuits the ||, which prevents the infinite loops from running. There's a lot more compiler Juju going on, so this is a simplistic view of the situation which is adequate for this example.

In a NON-short circuited environment, That expression would hang forever because both sides of the OR would be "evaluated" and the right side would hang.

If you're confused about the precedence, this is how things would evaluate in your original post if || had higher precedence than &&:

1st.) True || False = True
2nd.) True && 1st = True
3rd.) 2nd && false = false
Expression = False;

I can't remember if it goes right to left, or left to right, but either way the result would be the same. In your second post, if || had higher precendence:

1st.) 1||InfLoop();  Hang forever, but assuming it didn't
2nd.) 1 && 1st;
3rd.) 2nd && InfLoop(); Hang Forever

tl;dr: It's still precedence that's making the &&'s be evaluated first, but the compiler short circuits the OR as well. In essence, the compiler groups the order of operations like this (SIMPLISTIC VIEW, put down the pitchforks :-P)

1st.) Is 1&&1 True?
2nd.) Evaluate if the Left side of the operation is true, 
      if so, skip the second test and return True,
      Otherwise return the value of the second test(this is the OR)
3rd.) Is Inf() && Inf() True? (this would hang forever since 
      you have an infinite loop)

Update #2: "However, this example proves && DOES NOT have precedence, as the || is evaluated before the second &&. This shows that && and || have equal precedence and are evaluated in left-to-right order."

"If && had precedence it would evaluate the first && (1), then the second && (infinite loops) and hang the program. Since this does not happen, && is not evaluated before ||."

Let's cover these in detail.

We're talking about two distinct things here. Precedence, which determines the Order of Operations, and Short Circuiting, which is a compiler/language trick to save processor cycles.

Let's cover Precedence first. Precedence is short hand for "Order of Operations" In essence, given this statement: 1 + 2 * 3 in which order should the operations be grouped for evaluation?

Mathematics clearly defines the order of operations as giving multiplication higher precedence than addition.

1 + (2 * 3) = 1 + 2 * 3
2 * 3 is evaluated first, and then 1 is added to the result.
* has higher precedence than +, thus that operation is evaluated first.

Now, lets transition to boolean expressions: (&& = AND, || = OR)

true AND false OR true

C++ gives AND a higher precedence than OR, thus

(true AND false) OR true
true AND false is evaluated first, and then 
      used as the left hand for the OR statement

So, just on precedence, (true && true || false && false) will be operated on in this order:

((true && true) || (false && false)) = (true && true || false && false)
1st Comparison.) true && true
2nd Comparison.) false && false
3rd Comparison.) Result of 1st comparison || Result of Second

With me thus far? Now lets get into Short Circuiting: In C++, Boolean statements are what's called "short circuited". This means that the compiler will look at a given statement a choose the "best path" for evaluation. Take this example:

(true && true) || (false && false)
There is no need to evaluate the (false && false) if (true && true) 
equals true, since only one side of the OR statement needs to be true.
Thus, the compiler will Short Circuit the expression.  Here's the compiler's
Simplified logic:
1st.) Is (true && true) True?
2nd.) Evaluate if the Left side of the operation is true, 
      if so, skip the second test and return True,
      Otherwise return the value of the second test(this is the OR)
3rd.) Is (false && false) True? Return this value

As you can see, if (true && true) is evaluated TRUE, then there isn't a need to spend the clock cycles evaluating if (false && false) is true.

C++ Always short Circuts, but other languages provide mechanisms for what are called "Eager" operators.

Take for instance the programming language Ada. In Ada, "AND" and "OR" are "Eager" Operators..they force everything to be evaluated.

In Ada (true AND true) OR (false AND false) would evaluate both (true AND true) and (false AND false) before evaluating the OR. Ada Also gives you the ability to short circuit with AND THEN and OR ELSE, which will give you the same behavior C++ does.

I hope that fully answers your question. If not, let me know :-)

Update 3: Last update, and then I'll continue on email if you're still having issues.

"If short-circuiting the || operator occurs and short-circuits the execution of the second && expression, that means the || operator was executed BEFORE the second && operator. This implies left-to-right execution for && and || (not && precedence)."

Let's look at then this example:

(false && infLoop()) || (true && true) = true (Put a breakpoint in InfLoop and it won't get hit)
false && infLoop() || true && true = true  (Put a breakpoint in InfLoop and it won't get hit)
false || (false && true && infLoop()) || true = false (infLoop doesn't get hit)

If what you were saying was true, InfLoop would get hit in the first two. You'll also notice InfLoop() doesn't get called in the third example either.

Now, lets look at this:

(false || true && infLoop() || true);

Infloop gets called! If OR had higher precendence than &&, then the compiler would evaluate:

(false || true) && (infLoop() || true) = true;
(false || true) =true
(infLoop() || true = true (infLoop isn't called)

But InfLoop gets called! This is why:

(false || true && infLoop() || true);
1st Comparison.) true && InfLoop() (InfLoop gets called)
2nd Comparison.) False || 1st Comp (will never get here)
3rd Comparison.) 2nd Comp || true; (will never get here)

Precendece ONLY sets the grouping of operations. In this, && is greater than ||.

true && false || true && true gets grouped as
(true && false) || (true && true);

The Compiler Then comes along and determines what order it should execute the evaluation in to give it the best chance for saving cycles.

Consider: false && infLoop() || true && true
Precedence Grouping goes like this:
(false && infLoop()) || (true && true)
The compiler then looks at it, and decides it will order the execution in this order:
(true && true) THEN || THEN (false && InfLoop())

It's kindof a fact..and I don't know how else to demonstrate this. Precedence is determined by the language grammar rules. The Compiler's optimization is determined by each compiler..some are better than others, but All are free to reorder the grouped comparisons as it sees fit in order to give it the "best" chance for the fastest execution with the fewest comparisons.

Solution 4

&& does indeed have a higher precedence.

Solution 5

Two facts explain the behavior of both examples. First, the precedence of && is higher than ||. Second, both logical operators use short-circuit evaluation.

Precedence is often confounded with order of evaluation, but it is independent. An expression may have its individual elements evaluated in any order, as long as the final result is correct. In general for some operator, that means that the value on the left (LHS) may be evaluated either before or after the value on the right (RHS), as long as both are evaluated before the operator itself is applied.

The logical operators have a special property: in certain cases if one side evaluates to a specific value, then the operator's value is known regardless of the value on the other side. To make this property useful, the C language (and by extension every C-like language) has specified the logical operators to evaluate the LHS before the RHS, and further to only evaluate the RHS if its value is required to know the result of the operator.

So, assuming the usual definitions of TRUE and FALSE, TRUE && TRUE || FALSE && FALSE is evaluated starting at the left. The first TRUE doesn't force the result of the first &&, so the second TRUE is evaluated, and then the expression TRUE && TRUE is evaluated (to TRUE). Now, the || knows its LHS. Even better, its LHS has forced the result of the || to be known, so it skips evaluation of its entire RHS.

The exact same order of evaluation applies in the second case. Since the RHS of the || is irrelevant, it isn't evaluated and neither call to infiniteLoop() is made.

This behavior is by design, and is useful. For instance, you can write p && p->next knowing that the expression will never attempt to dereference a NULL pointer.

View more solutions

Comments

[Margus]

As soon as you evaluate true in myriad of or's it is short circuited and all subsequent expressions are disregarded.

[Alex S]

Short-circuit logic doesn't affect the result, it merely determines whether the entire expression is evaluated, or evaluation stops as soon as the final result is known.

[Andrew]

Is there a reference to the C++ standard where this can be found?

[Caladain]

That was in answer to Andrew :-)

[GManNickG]

@Andrew: Since you said "standard", no; the standard isn't free and so isn't available anywhere (unless you find scraps of it around the internet). You can, however, download the C++0x draft, which doesn't change C++ in this regard. However, with something as "common" as precedence you can be confident almost any site, though non-authoritative, will have the correct information.

[Chubsdad]

There is nothing called "TRUE" and "FALSE". It is "true" and "false". Secondly, "false && false" is not evaluated in this situation as || is a short circuit operator (and true && true evaluates to true)

[Cheers and hth. - Alf]

@Andrew: The C++ standard does not directly specify the precedence of operators. The (conceptual) precedence is implicit in the grammar, so you'd have to look at the grammar rules for a definitive reference (in this case it's the grammar production for a logical-and-expression). For example, precedence doesn't work for all cases of the comma operator. Precedence is a simplified view of the grammar. Still we think in terms of precedence, and you'll find precedence tables e.g. in MSDN and in Wikipedia. Cheers & hth.,

[cHao]

The very reason the operator can short-circuit at all, is because (true || X) == true. The part about false && false doesn't matter here, but it's still correct.

[Andrew]

I figured this much, but in this case it shows that && does not take precedence over || (instead left-to-right evaluation occurs).

[Caladain]

Sorry, been spending too much time in an environment that specifically doesn't short circuit, thus evaluating both sides of the statement in their entirety. TRUE and FALSE were just my short hand for Evaluating the statement, resolving into the boolean result (true or false) for an expression. TRUE could equal (X>2) or the keyword "true" or whatever you want. Same with FALSE.

[Andrew]

However, this example proves && DOES NOT have precedence, as the || is evaluated before the second &&. This shows that && and || have equal precedence and are evaluated in left-to-right order.

[Andrew]

If && had precedence it would evaluate the first && (1), then the second && (infinite loops) and hang the program. Since this does not happen, && is not evaluated before ||.

[Andrew]

If short-circuiting the || operator occurs and short-circuits the execution of the second && expression, that means the || operator was executed BEFORE the second && operator. This implies left-to-right execution for && and || (not && precedence).

[Andrew]

(true || (infiniteLoop() && infiniteLoop())

[Andrew]

If && had precedence it would attempt to evaluate two infinite loops. Instead, it short-circuits || (which is the next left-to-right operator) and short-circuits the rest of the expression.

[Billy ONeal]

@Andrew: Not true. || stops evaluating when it's left side is true; it never bothers evaluating the right side because the value of the whole expression is known.

[Adam Rosenfield]

This answer is WAY too long. It's technically accurate and thorough, but I'm not upvoting it because it's just way too verbose.

[Adam Rosenfield]

For the pedantic, see §5.14 [expr.log.and] and §5.15 [expr.log.or] of the C++03 standard. As @Alf mentioned, the precedence is implied by the grammar. The important clauses also state that (in the case of logical or), "|| guarantees left-to- right evaluation; moreover, the second operand is not evaluated if the first operand evaluates to true".

[Caladain]

(it's verbose because i have done like 3 answers on this..trying to explain it so the concept is understood :-(

[Steve Tjoa]

... one heck of a debut answer on Stack Overflow!

[Andrew]

This is helpful, but then how can you say && ever has precedence? Since || short-circuits, expressions involving && and || will always have to be evaluated in the left-to-right order you specify in your tree to determine if the expression short circuits... right?

[Andrew]

Is order of operations (which I may be misunderstanding as precedence) and precedence different? Your arithmetic example necessitates the two multiplications to be evaluated before the final addition, is that not what defines precedence?

[Antal Spector-Zabusky]

Order of operations is the same as precedence, yes. Hold on, I have another way to think about this that might help; I'll edit my question to include it.

[Antal Spector-Zabusky]

@Andrew: I added to my answer. I hope it helps clear things up.

[Antal Spector-Zabusky]

@Adam Rosenfield: You say "verbose" like it's a bad thing :-) I think this is an admirably complete and exhaustive answer. An emphatic +1 from me.

[user207421]

No it isn't a compiler optimization, it is a rule of the language.

[CB Bailey]

@Adam Rosenfield: It's not technically accurate. It has errors and is internally inconsistent. To pick a few points: "but All are free to reorder the grouped comparisons as it sees fit" is simply not true. Both && and || imply a sequence point and their second operand must not be evaluated if it is not needed. Also, equating "precedence" with "order of operations" is flat out misleading.

[filipe]

precedence doesn't necessarily mean the order in which operators are evaluated as much as it means how the expressions are "grouped" together. see RBerteig's answer below.

[filipe]

or refer to Antal S-Z's, he's written an entire lecture on the subject in his answer.

[Caladain]

Drop me an email Charles (or anyone else) with inconsistent points. I was writing off-the-cuff, and i have no doubt it could be cleaned up, or even expanded.

[Caladain]

@Charles - en.wikipedia.org/wiki/Order_of_operations. Order of operations (more formally precedence rule) is a rule used to unambiguously clarify which procedures should be performed first in a given mathematical expression. This is backed up by Programming and Problem Solving with C++ 4th Edition by Nell Dale | Chip Weems. The consistancy of my post should be cleaned up for future reference, and combined with Antal S-Z's post (i didn't think to do a parse tree. Knew i forgot something :-D) make up a pretty definitive answer on the subject.

[Caladain]

Also, it is my, admittedly limited, understanding that the short circuiting is not guaranteed by the language, and is a compiler trait that they could, or could not implement. Can more knowledgeable heads answer if a compiler HAS to implement boolean logic in a short circuiting fashion, or if it really is "up to the compiler" and everyone just happens to do it? Basically, is it in the language spec that it HAS to, or is just accepted practice that it does?

[CB Bailey]

@Caladain: I'm sorry but the wikipedia link that you've provided is simply not applicable to C++. In C++ the grammar rules (from which people infer precedence) control how complex expressions are interpreted in terms of grouping. They alone do not determine the order in which sub-expressions may be evaluated during execution. When you apply "order of operations" to a computer language rather than just abstract mathematical expressions you imply something which is just not true. Short-circuiting behaviour is guaranteed by the language. It's not an just an optimization.

[Caladain]

@Charles - Fair enough. Precedence rule is how most people think of these things (rule of thumb) and that term was internally consistent with university and my reference books. There's no debating that the grammar rules are the definitive source of these behaviors, but it's referred to as Order of Operations (precedence rule) in the books/web/etc because it mimics the behavior of the mathematical realm and is easier for people to grasp. It's a nitpicky thing that i think detracts from the overall question answer though, but if you'd like to take this convo to email, i'd be happy....(pt1)

[Caladain]

(pt2)...to hash out a finer detailed statement that covers both the language spec, reference books, and explains where the terms come from, what they mean, and how we use them in day-to-day operations to eliminate any future confusion (this answer combined with (Antal S-Z)'s covering basically every applicable vector for examining this issue for the lay-programmer) i'd be more than happy to do so.

[Caladain]

I'm getting Right hand evaluation as well in my sample code. _ || true = true; Just compiler optimization?

[Antal Spector-Zabusky]

That can't short-circuit, though. Of course it's true (for pure values), but the left-hand side will be evaluated. Try infiniteLoop() || true. If that does work, your compiler's probably optimizing out the loop.

[Caladain]

infiniteLoop() || True returns true. Indeed, i changed infinite loop to return a value based upon cin data (cheesy test) and slapped it full of breakpoints and none of them got hit. It didn't even bother doing the left side..optimized it completely out when it saw the true on the right.

[Antal Spector-Zabusky]

Bizarre. I don't get that behavior at all: compiling pastebin.com/zSKB1UBS with GCC 4.2.1 on OS X 10.6.3 without optimization never prints the second line; if I treat it as C++, it has the exact same behavior. The top line is the only one that's ever printed.

[Andrew]

Awesome, the tree was what helped me see how precedence works. The && operators are set up in the tree to be evaluated before the ||, but short-circuiting ensures || is evaluated first. All the answers were good, but I was looking for a different visualization and more importantly a visualization that the compiler would follow -- thanks again!

[darioo]

@Antal S-Z: what did you use to create that image? An image editor or something more sophisticated?

[Antal Spector-Zabusky]

@darioo: I used the LaTeX package qtree. I don't remember the exact LaTeX source, but it was pretty much \ttfamily \Tree[.+ [.* a b ] [.* c [.+ d e ]]] \Tree[.|| [.\&\& 1 1 ] [.\&\& infiniteLoop() infiniteLoop() ]]. I rendered it in LaTeXit, which is a nice Mac app for rendering snippets of LaTeX.