Posted by 
I think that the topic of short-circuiting is an under-appreciated one. In short, short-circuiting is simply ending an evaluation the instant it becomes false:
|
1 2 3 |
if(2 < 1 && 1 == 1) { /* stuff */ } if(2 > 1 || 1 == 1) { /* stuff */ } |
In this example, the second condition doesn’t get evaluated in either case.
In the first example, the compiler sees that both conditions have to be true in order for the complete evaluation to be true. Since the first condition is false, then logically, the whole thing is false so the second condition is ignored.
In the second example, the compiler sees that either condition can be true for the complete evaluation to be true. Since the first condition is true, then logically, the entire thing is true so the second condition is ignored.
Ok great, this is Programming 101 stuff, right?
Well of course it is. I think the majority of us understand that && and || are short-circuit operators and & and | are bit-wise operators, but based on what I see in several code bases, I’m not positive that many of us give enough credit to how simple and powerful the short circuit concept can be in day to day coding. Here’s why I just said “concept” instead of “operator” :
By thinking in terms of short-circuiting, we can potentially reduce load by making more efficient, logical statements. In other words, let’s not make our program work harder than it needs to. Here’s another short circuit example:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
foreach(Person person in People) { if(person.Age >= 18) { person.Image = _db.GetImage(person.Id); } if(person.Age >= 21) { person.CanDrink = true; } } |
The problem with this loop other than it’s questionable practicality (this is just for illustration) is that this loop will evaluate every single person over 18 at least twice: are they over 18, then are they over 21. What if we try to make this a little more efficient by skipping the entire block where possible. Logically, if the person being evaluated is under 18, then none of this logic would be run, right? Maybe something like this:
|
1 2 3 4 5 6 7 8 9 10 11 |
foreach(Person person in People) { if(person.Age < 18) continue; person.Image = _db.GetImage(person.Id); if(person.Age >= 21) { person.CanDrink = true; } } |
Again, the simplicity of this is just for illustration, but what we’ve done is short-circuited the loop. Since you have to be over the age of 18 in order to be over the age of 21, we’ve concluded that if you’re not over the age of 18, then this logic does not apply to you at all. Next person, please. The continue keyword tells the loop to skip the rest of the body and move on to the next iteration.
Prime Numbers
Short circuit operators and short circuiting loops isn’t all that is short-circuiting. I tend to think of short-circuiting as any logic where you interrupt the logic when a condition fails to apply to that logic.
So, I think we’ve all done the prime number quiz at least once in our careers. Here’s what I see most juniors come up with:
Example 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
static void Main(string[] args) { // output all prime numbers between 1 and 100 for (var i = 2; i <= 100; i++) { var isPrime = true; for (var j = 2; j < i; j++) { if (i%j == 0) isPrime = false; } if(isPrime) Console.WriteLine("{0} is a prime number.", i); } Console.ReadKey(); } |
Now, this makes logical sense, especially if you haven’t done this before and/or haven’t had an opportunity to optimize it. Basically you take your number and then you test every number between 1 and your number to see if they divide evenly. If any of them divide evenly, then your number is not a prime number.
The problem with this is that it will test every number in the number set which is 2 through 100. If the range were 2 through 1 million, then it would test every number in that set as well. There’s no short-circuit. Let’s take a different approach? How about first, we break it into something a bit more manageable, and then apply some short circuiting.
Example 2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
static void Main(string[] args) { // output all prime numbers between 1 and 100 foreach (var number in Enumerable.Range(1, 100)) { if(IsPrime(number)) Console.WriteLine("{0} is a prime number.", number); } Console.ReadKey(); } private static bool IsPrime(int number) { if (number < 2) { return false; } // short circuit if (number == 2) { return true; } // short circuit if (number % 2 == 0) { return false; } // short circuit for (var d = 3; d < number; d += 2) { if (number % d == 0) return false; // short circuit } return true; } |
In the IsPrime function, we’ve set 3 easy short-circuits. We know that numbers less than 1 are not prime. Next, we know that 2 is the only even prime number. Then we also know that if the number divides evenly by 2, it is not a prime number. So by calling these things out early in the process, we can eliminate the need to run the loop, saving us some valuable cycles. Now if we get past all of these short circuits, then we can run through the loop as before and test the remaining numbers. If we wanted to take it further, we can apply some math knowledge to further reduce the number set size:
Example 3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
static void Main(string[] args) { // output all prime numbers between 1 and 100 foreach (var number in Enumerable.Range(3, 100)) { if(IsPrime(number)) Console.WriteLine("{0} is a prime number.", number); } Console.ReadKey(); } private static bool IsPrime(int number) { if (number < 2) { return false; } // short circuit if (number == 2) { return true; } // short circuit if (number % 2 == 0) { return false; } // short circuit for (var d = 3; d * d <= number; d += 2) { if (number % d == 0) return false; // short circuit } return true; } |
By changing our loop condition to d * d <= number we’re eliminating the squares of the number (and everything above it) which would have been basically testing the same number multiple times. This isn’t a short-circuit per say, but I think it goes along with the “eliminate unnecessary evaluations” theme.
Conclusion
So basically, we need to remind ourselves to cut out the fat, especially in iterative logic. Any time we can eliminate unnecessary evaluations, now matter how seemingly insignificant, we could potentially gain mountains of processing time. Just for fun, I went and bench-marked these three examples by processing 0 through 1 million (0xF4240) and here’s what I ended up with:
Example 1: 1,579,187 ms (26 minutes!)
Example 2: 64,797 ms
Example 3a: 3,507 ms
Example 3b: (without the first 3 short-circuits): 7,364 ms
I assume your code is C#, if so, & and } are not bitwise operators in a Boolean expression, they are non-short-circuiting logical operators.
Meaning:
if (false & DoSomething()) calls DoSomething().
if (false && DoSomething()) does NOT call DoSomething.
Well you’re half right. You’re right in that they are “logical operators”, but you are wrong in saying they are not bitwise operators. As per MSDN (and pretty any resource I’ve ever seen — google “bitwise and” and see what you get), they are bitwise when used with integral types and logical when used with boolean operands. But they are still referred to as bitwise operators..
Case in point, go see what 0xFFFF | 0xAAAA comes out to. I bet you it is 0xFFFF. And I bet 0xFFFF & 0xAAAA comes out to 0xAAAA. And I bet you if you do 0xFF ^ 0xFF (bitwise XOR) you’ll get 0. But if it “evaluated” both sides, how could there be more than one bit on either side of the | operator? Because the operator isn’t “calling” anything. It’s comparing 2 values but in order to get to the second value in your scenario, it has to run your function so that it can use its return value (functions can be treated as the value that they return).
With your argument that it’s about evaluating both sides (vs. short-circuiting), it would imply that I could do something like 0xFFFF || 0xAAAA (using the short-circuit operator) but you can’t because it doesn’t actually make any sense because neither 0xFFFF nor 0xAAAA can be associated with a boolean value (true or false; 0 or 1). Short-circuit operators are purely logical and also referred to as “Conditional Logical Operators”
To further disprove the idea that the operator is “calling” anything, try to do if(true | DoThing()) where DoThing returns void. Not only does it not call, it doesn’t even compile. Yet, if(true | null) *does* compile. In fact true | null = true and true & null = null. Why? Because void is a type and null is a value.
Sure, double the operators gives you a short-circuit (I think everyone knows that), but I’m trying to think of a (good) scenario where you’d want to force it into ‘logical mode” and evaluate both sides by using a bitwise operator with boolean operands. If I ever saw your example in production C# code, it’d never make it through code review because that is just plain bad code. So what you’ve described is not what the operator is, but rather how the compiler gets around to using it. Using a bitwise/logical operator as a way to “not short-circuit” is a hack, not a definition.