5.2. Boolean Data and OperatorsAs 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.
George Boole 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:
Conditional statement For this reason, boolean expressions are also called conditions. Along the same lines, a boolean variable can be used as a flag or 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 flag 5.2.1. Boolean (or Logical) OperationsLike all the other simple data types, the boolean type consists of certain datathe values true and falseand certain actions or operations that can be performed on the data. For the boolean type there are four basic operations: AND (signified by &&), OR (signified by ||), EXCLUSIVE-OR (signified by L), and NOT (signified by !). These are defined in the truth table shown in Table 5.1. A truth table 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.
Data and operations 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 operatorthat is, it requires two operands, o1 and o2. If both o1 and o2 are true, then (o1 && o2) is true (row 1). If either o1 or o2 or both o1 and o2 are false, then the expression (o1 && o2) is false (rows 24).
Binary operator The boolean OR operation (column 4 of Table 5.1) is also a binary operation. If both o1 and o2 are false, then (o1 || o2) is false (row 4). If either o1 or o2 or both o1 and o2 are true, then the expression (o1 || o2) is true (rows 13). Thus, the only case in which (o1 || 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 unary operatorit takes only one operandand it simply reverses the truth value of its operand. Thus, if o1 is true, !o1 is false, and vice versa.
Unary operator 5.2.2. Precedence and AssociativityIn 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 || first or the && first. If we evaluate the || 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 && operator has higher precedence than the || 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 || 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.
Parentheses supersede 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 the 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 Java Programming Tip: Parentheses
In addition to operator precedence, it is necessary to know about an operator's associativity in order to evaluate boolean expressions of the form (op1 || op2 || op3). Should this expression be evaluated as ((op1 || op2) || op3) or as (op1 || (op2 || 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 5.2.3. Short-Circuit EvaluationAnother 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 be evaluated. Similarly, in the expression expr1 || expr2 if expr1 is true, then the OR expression must be true, so expr2 need not be evaluated. In addition to being a more efficient way 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 variablethat 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.game-Over(). 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. Self-Study Exercise
5.2.4. Using Booleans in OneRowNimNow that we have introduced the boolean data type, let's use it to improve the OneRowNim class, the latest version of which, from Chapter 3, is given in Figure 3.16. Previously we used an int variable, player, to represent whose turn it is. For a two-person game, such as One-Row Nim, a boolean variable is well suited for this purpose, because it can toggle between true and false. For example, let's declare a variable, onePlaysNext, and initialize it to true, to represent the fact that player 1 will play first: private boolean onePlaysNext = true; When onePlaysNext is true, it will be player 1's turn. When it is false, it will be player 2's turn. Note that we are deliberately remaining uncommitted as to whether one or the other player is the computer. Given this new variable, it is necessary to redefine the methods that previously used the player variable. The first method that needs revision is the constructor: public OneRowNim(int sticks, int starter) { nSticks = sticks; onePlaysNext = (starter == 1); } // OneRowNim() constructor3 In the constructor, the starter parameter is used with a value of 1 or 2 to set which player goes first. Note how we use an assignment statement to set onePlaysNext to true if starter equals 1; otherwise it is set to false. The assignment statement first evaluates the expression on its right-hand side (starter == 1). Because this is a boolean expression, it will have a value of true or false, which will be assigned to onePlaysNext. Thus, the assignment statement is equivalent to the following if/else statement: if (player == 1) onePlaysNext = true; else onePlaysNext = false; The remaining changes are shown in Figure 5.2. There are only two instance methods that need revision to accommodate the use of boolean variables. The takeSticks() method contains two revisions. The first uses the boolean OR operator to test whether a move is valid: public boolean takeSticks(int num) { if (num < 1 || num > 3 || num > nSticks) return false; // Error else // Valid move { nSticks = nSticks - num; onePlaysNext = !onePlaysNext; return true; } // else } // takeSticks() Figure 5.2. The revised OneRowNim uses a boolean variable to keep track of whose turn it is.
It also uses the boolean NOT operator to toggle the value of onePlaysNext, to switch to the other player's turn: onePlaysNext = !onePlaysNext; Finally, the getPlayer() method now uses an if/else statement to return either 1 or 2 depending on whose turn it is: public int getPlayer() { if (onePlaysNext) return 1; else return 2; } // getPlayer() |