5.1: Boolean Data and Operators

As we learned in Chapter 1, the boolean type is one of Java’s primitive types. For this type, there are only two possible values, true and false. The boolean type is derived from the work of British mathematician George Boole, who in the 1850s, developed an algebra to process logical expressions such as p and q. Such boolean expressions produce a value that is either true or false. Every modern programming language provides some means of representing boolean expressions.

The boolean type has several important uses. As we saw in Chapter 1, expressions of the form num == 7 and 5 < 7 have boolean values. Similarly, as we saw in Chapter 3, the boolean type is also used to represent the condition in the if statement:

\[\matrix{ \hbox{\tt if} & ( \hbox{\it boolean expression} )\hfill\cr & \hbox{\it statement} ;\hfill\cr }\]

For this reason, boolean expressions are also called conditions. Along these same lines, a boolean variable can be used as a flag or a signal to “remember” whether or not a certain condition holds. For example, in the following code fragment, we use isDone to mark when a particular process is completed:

boolean isDone = false; // Initialize the flag
...                     // Do some processing task
isDone = true;          // Set flag when the task done
...                     // Do some other stuff
if (isDone)             // Check if finished the task
...                     //  If so, do something
else
...                     //  Or, do something else

Boolean (or Logical) Operations

Like all the other simple data types, the boolean type consists of certain data—the values true and false—and certain actions or operations that can be performed on those data. For the boolean type there are four basic operations: AND (signified by &&), OR (signified by \(\mid\mid\)), EXCLUSIVE-OR (signified by \(\wedge\)), and NOT (signified by !). These are defined in the truth table shown in Table 5.1. A truth tables defines boolean operators by giving their values in all possible situations. The first two columns of the table give possible boolean values for two operands, o1 and o2. An operand is a value used in an operation. Note that each row gives a different value assignment to the two operands, so that all possible assignments are represented. The remaining columns give the values that result for the various operators given the assignment of values to o1 and o2.

llllll
o1&o2&o1 && o2&o1 \(\mid\mid\) o2&o1 \(\wedge\) o2&!o1

true&true&true&true&false&false&false&false&true&true&false&true&false&true&true&true&false&false&false&false&true

To see how to read this table, let’s look at the AND operation, which is defined in column 3. The AND operator is a binary operator—that is, it requires two operands, and o2. If both o1 and o2 are true, then (o1 && o2) is true (row1). If either o1 or o2 or both o1 and o2 are false, then the expression (o1 && o2) is false (rows 2 and 3). The only case in which (o1 && o2) is true is when both o1 and o2 are true (row 4).

The boolean OR operation (column 4 of Table 5.1) is also a binary operation. If both o1 and o2 are false, then \((o1 \mid\mid o2)\) is false (row 4). If either o1 or o2 or both o1 and o2 are true, then the expression \((o1 \mid\mid o2)\) is true (rows 1-3). Thus, the only case in which \((o1 \mid\mid o2)\) is false is when both o1 and o2 are false.

The boolean EXCLUSIVE-OR operation (column 5 of Table 5.1) is a binary operation, which differs from the OR operator in that it is true when either o1 or o2 is true (rows 2 and 3), but it is false when both o1 and o2 are true (row 1).

The NOT operation (the last column of Table 5.1) is a —it takes only one operand—and it simply reverses the truth value of its operand. Thus, if o1 is true, !o1 is false, and vice versa.

Precedence and Associativity

In order to evaluate complex boolean expressions, it is necessary to understand the order in which boolean operations are carried out by the computer. For example, what is the value of the following expression?

true || true && false

The value of this expression depends on whether we evaluate the \(\mid\mid\) first or the && first. If we evaluate the \(\mid\mid\) first, the expression’s value will be false; if we evaluate the && first, the expression’s value will be true. In the following example, we use parentheses to force one operation to be done before the other:

EXPRESSION                EVALUATION
----------                ----------
( true || true ) && false ==> true && false ==> false
true || ( true && false ) ==> true || false ==> true

As these evaluations show, we can use parentheses to force one operator or the other to be evaluated first. However, in Java, the && has higher precedence than the \(\mid\mid\) operator. Therefore, the second alternative corresponds to the default interpretation that Java would apply to the expression that has no parentheses. In other words, given the expression \(true \; \mid\mid \; true \; \&\& \; false\), the AND operation would be evaluated before the OR operation even though the OR operator occurs first (i.e., to the left) in the unparenthesized expression.

[2pt] Precedence Order	Operator	Operation
[-4pt]
[2pt] 1	( )	Parentheses
2	!	NOT
3	\(\wedge\)	EXCLUSIVE-OR
4	&&	AND
5	||	OR
[-4pt]

As this example illustrates, the boolean operators have a built-in precedence order which is used to determine how boolean expressions are to be evaluated (Table 5.2). A simple method for evaluating an expression is to parenthesize the expression and then evaluate it. For example, to evaluate the complex expression

true || !false ^ false && true

we would first parenthesize it according to the precedence rules set out in Table 5.2, which gives the following expression:

true || (((!false) ^ false) && true)

We can then evaluate this fully parenthesized expression, step by step, starting at the innermost parentheses:

Step 1. true || ((true ^ false) && true)
Step 2. true || (true && true)
Step 3. true || true
Step 4. true

In addition to operator precedence, it is necessary to know about anoperator’s associativity in order to evaluate boolean expressions of the form \({\tt (op1 \mid\mid op2 \mid\mid op3)}\). Should this expression be evaluated as \({\tt ((op1 \mid\mid op2) \mid\mid op3)}\) or as \({\tt (op1 \mid\mid (op2 \mid\mid op3))}\)? The binary boolean operators all associate from left to right. Thus, the expressions

true ^ true ^ true   // Same as: (true ^ true) ^ true
true && true && true // Same as: (true && true) && true
true || true || true // Same as: (true || true) || true

would be evaluated as follows:

EXPRESSION               EVALUATION
----------------         -----------------
(true ^ true)  ^ true    ==> false ^ true  ==> true
(true && true)  && true  ==> true  && true ==> true
(true || true)  || true  ==> true  || true ==> true

Short-Circuit Evaluation

Another important feature of the boolean operators is that they utilize a form of evaluation known as short-circuit evaluation. In short-circuit evaluation, a boolean expression is evaluated from left to right, and the evaluation is discontinued as soon as the expression’s value can be determined, regardless of whether it contains additional operators and operands. For example, in the expression

  expr1 && expr2

if expr1 is false, then the AND expression must be false, so expr2 need not evaluated. Similarly, in the expression

 expr1 || expr2

if expr1 is true, then the OR expression must be true, so expr2 need not evaluated.

In addition to being a more efficient form of evaluating boolean expressions, short-circuit evaluation has some practical uses. For example, we can use short-circuit evaluation to guard against null pointer exceptions. Recall from Chapter 2 that a null pointer exception results when you try to use an uninstantiated reference variable—that is, a reference variable that has not been assigned an object. For example, if we declare a OneRowNim variable without instantiating it and then try to use it, a null pointer exception will result:

OneRowNim game;        // Uninstantiated Reference
if (!game.gameOver())  // Null pointer exception
    game.takeSticks(num);

In this code, a null pointer exception results when we use game in the method call game.gameOver(). We can use short-circuit evaluation to prevent the exception from occurring:

if ((game != null) && (!game.gameOver())
    game.takeSticks(num);

In this case, because game != null is false, neither method call involving game is made, thus avoiding the exception.