Java Puzzle 1: Oddity

```
public static boolean isOdd(int i) {
return i % 2 == 1;
```

} Java Puzzles Solution 1: Oddity

An odd number can be defined as an integer that is divisible by 2 with a remainder of 1. The expression i % 2 computes the remainder when i is divided by 2, so it would seem that this program ought to work. Unfortunately, it doesn’t; it returns the wrong answer one quarter of the time.

Why one quarter? Because half of all int values are negative, and the isOdd method fails for all negative odd values. It returns false when invoked on any negative value, whether even or odd.

This is a consequence of the definition of Java’s remainder operator (%). It is defined to satisfy the following identity for all int values a and all nonzero int values b:

The isOdd method and the definition of the term odd on which it was based both assume that all remainders are positive. Although this assumption makes sense for some kinds of division [Boute92], Java’s remainder operation is per- fectly matched to its integer division operation, which discards the fractional part of its result.

When i is a negative odd number, i % 2 is equal to -1 rather than 1, so the isOdd method incorrectly returns false. To prevent this sort of surprise, test that your methods behave properly when passed negative, zero, and positive val- ues for each numerical parameter.

The problem is easy to fix. Simply compare i % 2 to 0 rather than to 1, and reverse the sense of the comparison:

This is a consequence of the definition of Java’s remainder operator (%). It is defined to satisfy the following identity for all int values a and all nonzero int values b:

```
(a / b) * b + (a % b) == a
```

In other words, if you divide a by b, multiply the result by b, and add the remain- der, you are back where you started [JLS 15.17.3]. This identity makes perfect sense, but in combination with Java’s truncating integer division operator [JLS 15.17.2], it implies that when the remainder operation returns a nonzero result, it has the same sign as its left operand. The isOdd method and the definition of the term odd on which it was based both assume that all remainders are positive. Although this assumption makes sense for some kinds of division [Boute92], Java’s remainder operation is per- fectly matched to its integer division operation, which discards the fractional part of its result.

When i is a negative odd number, i % 2 is equal to -1 rather than 1, so the isOdd method incorrectly returns false. To prevent this sort of surprise, test that your methods behave properly when passed negative, zero, and positive val- ues for each numerical parameter.

The problem is easy to fix. Simply compare i % 2 to 0 rather than to 1, and reverse the sense of the comparison:

```
public static boolean isOdd(int i) {
return i % 2 != 0;
```

}
If you are using the isOdd method in a performance-critical setting, you would be better off using the bitwise AND operator (&) in place of the remainder operator:

The second version may run much faster than the first, depending on what platform and virtual machine you are using, and is unlikely to run slower. As a general rule, the divide and remainder operations are slow compared to other arithmetic and logical operations. It’s a bad idea to optimize prematurely, but in this case, the faster version is as clear as the original, so there is no reason to pre- fer the original.

In summary, think about the signs of the operands and of the result whenever you use the remainder operator. The behavior of this operator is obvious when its operands are nonnegative, but it isn’t so obvious when one or both operands are negative.

Java Puzzle 2: Time for a Change

Consider the following word problem:

Tom goes to the auto parts store to buy a spark plug that costs $1.10, but all he has in his wallet are two-dollar bills. How much change should he get if he pays for the spark plug with a two-dollar bill?

Here is a program that attempts to solve the word problem. What does it print?

```
public static boolean isOdd(int i) {
return (i & 1) != 0;
```

} The second version may run much faster than the first, depending on what platform and virtual machine you are using, and is unlikely to run slower. As a general rule, the divide and remainder operations are slow compared to other arithmetic and logical operations. It’s a bad idea to optimize prematurely, but in this case, the faster version is as clear as the original, so there is no reason to pre- fer the original.

In summary, think about the signs of the operands and of the result whenever you use the remainder operator. The behavior of this operator is obvious when its operands are nonnegative, but it isn’t so obvious when one or both operands are negative.

Java Puzzle 2: Time for a Change

Consider the following word problem:

Tom goes to the auto parts store to buy a spark plug that costs $1.10, but all he has in his wallet are two-dollar bills. How much change should he get if he pays for the spark plug with a two-dollar bill?

Here is a program that attempts to solve the word problem. What does it print?

```
public class Change {
public static void main(String args[]) {
```

```
System.out.println(2.00 - 1.10);
}
```

}
Java Puzzle Solution 2: Time for a Change

Naively, you might expect the program to print 0.90, but how could it know that you wanted two digits after the decimal point? If you know something about the rules for converting double values to strings, which are specified by the documen- tation for Double.toString [Java-API], you know that the program prints the shortest decimal fraction sufficient to distinguish the double value from its near- est neighbor, with at least one digit before and after the decimal point. It seems reasonable, then, that the program should print 0.9. Reasonable, perhaps, but not correct. If you ran the program, you found that it prints 0.8999999999999999.

The problem is that the number 1.1 can’t be represented exactly as a double, so it is represented by the closest double value. The program subtracts this value from 2. Unfortunately, the result of this calculation is not the closest double value to 0.9. The shortest representation of the resulting double value is the hideous number that you see printed.

More generally, the problem is that not all decimals can be represented exactly using binary floating-point. If you are using release 5.0 or a later release, you might be tempted to fix the program by using the printf facility to set the precision of the output:

One way to solve the problem is to use an integral type, such as int or long, and to perform the computation in cents. If you go this route, make sure the integral type is large enough to represent all the values you will use in your program. For this puzzle, int is ample. Here is how the println looks if we rewrite it using int values to represent monetary values in cents. This version prints 90 cents, which is the right answer:

The problem is that the number 1.1 can’t be represented exactly as a double, so it is represented by the closest double value. The program subtracts this value from 2. Unfortunately, the result of this calculation is not the closest double value to 0.9. The shortest representation of the resulting double value is the hideous number that you see printed.

More generally, the problem is that not all decimals can be represented exactly using binary floating-point. If you are using release 5.0 or a later release, you might be tempted to fix the program by using the printf facility to set the precision of the output:

```
// Poor solution - still uses binary floating-point!
```

```
System.out.printf("%.2f%n", 2.00 - 1.10);
```

This prints the right answer but does not represent a general solution to the under- lying problem: It still uses double arithmetic, which is binary floating-point. Floating-point arithmetic provides good approximations over a wide range of val- ues but does not generally yield exact results. Binary floating-point is particu- larly ill-suited to monetary calculations, as it is impossible to represent 0.1—or any other negative power of 10—exactly as a finite-length binary fraction [EJ Item 31]. One way to solve the problem is to use an integral type, such as int or long, and to perform the computation in cents. If you go this route, make sure the integral type is large enough to represent all the values you will use in your program. For this puzzle, int is ample. Here is how the println looks if we rewrite it using int values to represent monetary values in cents. This version prints 90 cents, which is the right answer:

```
System.out.println((200 - 110) + " cents");
```

Another way to solve the problem is to use BigDecimal, which performs exact decimal arithmetic. It also interoperates with the SQL DECIMAL type via JDBC. There is one caveat: Always use the BigDecimal(String) constructor, never BigDecimal(double). The latter constructor creates an instance with the exact value of its argument: new BigDecimal(.1) returns a BigDecimal repre- senting 0.1000000000000000055511151231257827021181583404541015625. Using BigDecimal correctly, the program prints the expected result of 0.90:

This version is not terribly pretty, as Java provides no linguistic support for BigDecimal. Calculations with BigDecimal are also likely to be slower than those with any primitive type, which might be an issue for some programs that make heavy use of decimal calculations. It is of no consequence for most programs.

In summary, avoid float and double where exact answers are required; for monetary calculations, use int, long, or BigDecimal. For language design- ers, consider providing linguistic support for decimal arithmetic. One approach is to offer limited support for operator overloading, so that arithmetic operators can be made to work with numerical reference types, such as BigDecimal. Another approach is to provide a primitive decimal type, as did COBOL and PL/I.

Java Puzzle 3: Long Division

This puzzle is called Long Division because it concerns a program that divides two long values. The dividend represents the number of microseconds in a day; the divisor, the number of milliseconds in a day. What does the program print?

```
import java.math.BigDecimal;
public class Change {
```

```
public static void main(String args[]) {
System.out.println(new BigDecimal("2.00").
```

```
subtract(new BigDecimal("1.10")));
```

} } This version is not terribly pretty, as Java provides no linguistic support for BigDecimal. Calculations with BigDecimal are also likely to be slower than those with any primitive type, which might be an issue for some programs that make heavy use of decimal calculations. It is of no consequence for most programs.

In summary, avoid float and double where exact answers are required; for monetary calculations, use int, long, or BigDecimal. For language design- ers, consider providing linguistic support for decimal arithmetic. One approach is to offer limited support for operator overloading, so that arithmetic operators can be made to work with numerical reference types, such as BigDecimal. Another approach is to provide a primitive decimal type, as did COBOL and PL/I.

Java Puzzle 3: Long Division

This puzzle is called Long Division because it concerns a program that divides two long values. The dividend represents the number of microseconds in a day; the divisor, the number of milliseconds in a day. What does the program print?

```
public class LongDivision {
public static void main(String[] args) {
```

} }

```
final long MICROS_PER_DAY = 24 * 60 * 60 * 1000 * 1000;
final long MILLIS_PER_DAY = 24 * 60 * 60 * 1000;
System.out.println(MICROS_PER_DAY / MILLIS_PER_DAY);
```

Java Puzzle Solution 3: Long Division

This puzzle seems reasonably straightforward. The number of milliseconds per day and the number of microseconds per day are constants. For clarity, they are expressed as products. The number of microseconds per day is (24 hours/day · 60 minutes/hour · 60 seconds/minute · 1,000 milliseconds/second · 1,000 microsec- onds/millisecond). The number of milliseconds per day differs only in that it is missing the final factor of 1,000. When you divide the number of microseconds per day by the number of milliseconds per day, all the factors in the divisor cancel out, and you are left with 1,000, which is the number of microseconds per milli- second. Both the divisor and the dividend are of type long, which is easily large enough to hold either product without overflow. It seems, then, that the program must print 1000. Unfortunately, it prints 5. What exactly is going on here?

The problem is that the computation of the constant MICROS_PER_DAY does overflow. Although the result of the computation fits in a long with room to spare, it doesn’t fit in an int. The computation is performed entirely in int arithmetic, and only after the computation completes is the result promoted to a long. By then, it’s too late: The computation has already overflowed, returning a value that is too low by a factor of 200. The promotion from int to long is a widening prim- itive conversion [JLS 5.1.2], which preserves the (incorrect) numerical value. This value is then divided by MILLIS_PER_DAY, which was computed correctly because it does fit in an int. The result of this division is 5.

So why is the computation performed in int arithmetic? Because all the fac- tors that are multiplied together are int values. When you multiply two int val- ues, you get another int value. Java does not have target typing, a language feature wherein the type of the variable in which a result is to be stored influences the type of the computation.

It’s easy to fix the program by using a long literal in place of an int as the first factor in each product. This forces all subsequent computations in the expres- sion to be done with long arithmetic. Although it is necessary to do this only in the expression for MICROS_PER_DAY, it is good form to do it in both products. Sim- ilarly, it isn’t always necessary to use a long as the first value in a product, but it is

The problem is that the computation of the constant MICROS_PER_DAY does overflow. Although the result of the computation fits in a long with room to spare, it doesn’t fit in an int. The computation is performed entirely in int arithmetic, and only after the computation completes is the result promoted to a long. By then, it’s too late: The computation has already overflowed, returning a value that is too low by a factor of 200. The promotion from int to long is a widening prim- itive conversion [JLS 5.1.2], which preserves the (incorrect) numerical value. This value is then divided by MILLIS_PER_DAY, which was computed correctly because it does fit in an int. The result of this division is 5.

So why is the computation performed in int arithmetic? Because all the fac- tors that are multiplied together are int values. When you multiply two int val- ues, you get another int value. Java does not have target typing, a language feature wherein the type of the variable in which a result is to be stored influences the type of the computation.

It’s easy to fix the program by using a long literal in place of an int as the first factor in each product. This forces all subsequent computations in the expres- sion to be done with long arithmetic. Although it is necessary to do this only in the expression for MICROS_PER_DAY, it is good form to do it in both products. Sim- ilarly, it isn’t always necessary to use a long as the first value in a product, but it is

Puzzle 4: It’s Elementary 11 good form to do so. Beginning both computations with long values makes it clear

that they won’t overflow. This program prints 1000 as expected:

} }

The lesson is simple: When working with large numbers, watch out for overflow—it’s a silent killer. Just because a variable is large enough to hold a result doesn’t mean that the computation leading to the result is of the correct type. When in doubt, perform the entire computation using long arithmetic.

The lesson for language designers is that it may be worth reducing the likeli- hood of silent overflow. This could be done by providing support for arithmetic that does not overflow silently. Programs could throw an exception instead of overflowing, as does Ada, or they could switch to a larger internal representation automatically as required to avoid overflow, as does Lisp. Both of these approaches may have performance penalties associated with them. Another way to reduce the likelihood of silent overflow is to support target typing, but this adds significant complexity to the type system [Modula-3 1.4.8].

Java Puzzle 4: It’s Elementary

OK, so the last puzzle was a bit tricky, but it was about division. Everyone knows that division is tough. This program involves only addition. What does it print?

that they won’t overflow. This program prints 1000 as expected:

```
public class LongDivision {
public static void main(String[] args) {
```

final long MICROS_PER_DAY = 24L * 60 * 60 * 1000 * 1000; final long MILLIS_PER_DAY = 24L * 60 * 60 * 1000; System.out.println(MICROS_PER_DAY / MILLIS_PER_DAY); } }

The lesson is simple: When working with large numbers, watch out for overflow—it’s a silent killer. Just because a variable is large enough to hold a result doesn’t mean that the computation leading to the result is of the correct type. When in doubt, perform the entire computation using long arithmetic.

The lesson for language designers is that it may be worth reducing the likeli- hood of silent overflow. This could be done by providing support for arithmetic that does not overflow silently. Programs could throw an exception instead of overflowing, as does Ada, or they could switch to a larger internal representation automatically as required to avoid overflow, as does Lisp. Both of these approaches may have performance penalties associated with them. Another way to reduce the likelihood of silent overflow is to support target typing, but this adds significant complexity to the type system [Modula-3 1.4.8].

Java Puzzle 4: It’s Elementary

OK, so the last puzzle was a bit tricky, but it was about division. Everyone knows that division is tough. This program involves only addition. What does it print?

```
public class Elementary {
public static void main(String[] args) {
```

```
System.out.println(12345 + 5432l);
}
```

}
Java Puzzle Solution 4: It’s Elementary

On the face of it, this looks like an easy puzzle—so easy that you can solve it without pencil or paper. The digits of the left operand of the plus operator ascend from 1 to 5, and the digits of the right operand descend. Therefore, the sums of corresponding digits remain constant, and the program must surely print 66666. There is only one problem with this analysis: When you run the program, it prints 17777. Could it be that Java has an aversion to printing such a beastly number? Somehow this doesn’t seem like a plausible explanation.

On the face of it, this looks like an easy puzzle—so easy that you can solve it without pencil or paper. The digits of the left operand of the plus operator ascend from 1 to 5, and the digits of the right operand descend. Therefore, the sums of corresponding digits remain constant, and the program must surely print 66666. There is only one problem with this analysis: When you run the program, it prints 17777. Could it be that Java has an aversion to printing such a beastly number? Somehow this doesn’t seem like a plausible explanation.

Things are seldom what they seem. Take this program, for instance. It doesn’t say what you think it does. Take a careful look at the two operands of the + opera- tor. We are adding the int value 12345 to the long value 5432l. Note the subtle difference in shape between the digit 1 at the beginning of the left operand and the lowercase letter el at the end of the right operand. The digit 1 has an acute angle between the horizontal stroke, or arm, and the vertical stroke, or stem. The lower- case letter el, by contrast, has a right angle between the arm and the stem.

Before you cry “foul,” note that this issue has caused real confusion. Also note that the puzzle’s title contained a hint: It’s El-ementary; get it? Finally, note that there is a real lesson here. Always use a capital el (L) in long literals, never a lowercase el (l). This completely eliminates the source of confusion on which the puzzle relies:

System.out.println(12345 + 5432L);

Similarly, avoid using a lone el (l) as a variable name. It is difficult to tell

by looking at this code snippet whether it prints the list l or the number 1:

// Bad code - uses el (l) as a variable name List l = new ArrayList(); l.add("Foo");

System.out.println(1);

In summary, the lowercase letter el and the digit 1 are nearly identical in most typewriter fonts. To avoid confusing the readers of your program, never use a low- ercase el to terminate a long literal or as a variable name. Java inherited much from the C programming language, including its syntax for long literals. It was probably a mistake to allow long literals to be written with a lowercase el.

Before you cry “foul,” note that this issue has caused real confusion. Also note that the puzzle’s title contained a hint: It’s El-ementary; get it? Finally, note that there is a real lesson here. Always use a capital el (L) in long literals, never a lowercase el (l). This completely eliminates the source of confusion on which the puzzle relies:

System.out.println(12345 + 5432L);

Similarly, avoid using a lone el (l) as a variable name. It is difficult to tell

by looking at this code snippet whether it prints the list l or the number 1:

// Bad code - uses el (l) as a variable name List

System.out.println(1);

In summary, the lowercase letter el and the digit 1 are nearly identical in most typewriter fonts. To avoid confusing the readers of your program, never use a low- ercase el to terminate a long literal or as a variable name. Java inherited much from the C programming language, including its syntax for long literals. It was probably a mistake to allow long literals to be written with a lowercase el.

Java Puzzle 5: The Joy of Hex

The following program adds two hexadecimal, or “hex,” literals and prints the result in hex. What does the program print?

The following program adds two hexadecimal, or “hex,” literals and prints the result in hex. What does the program print?

```
public class JoyOfHex {
public static void main(String[] args) {
```

} }

```
System.out.println(
Long.toHexString(0x100000000L + 0xcafebabe));
```

Puzzle 5: The Joy of Hex 13

Java Puzzle Solution 5: The Joy of Hex

It seems obvious that the program should print 1cafebabe. After all, that is the sum of the hex numbers 10000000016 and cafebabe16. The program uses long arithmetic, which permits 16 hex digits, so arithmetic overflow is not an issue. Yet, if you ran the program, you found that it prints cafebabe, with no leading 1 digit. This output represents the low-order 32 bits of the correct sum, but some- how the thirty-third bit gets lost. It is as if the program were doing int arithmetic instead of long, or forgetting to add the first operand. What’s going on here?

Decimal literals have a nice property that is not shared by hexadecimal or octal literals: Decimal literals are all positive [JLS 3.10.1]. To write a negative decimal constant, you use the unary negation operator (-) in combination with a decimal literal. In this way, you can write any int or long value, whether positive or negative, in decimal form, and negative decimal constants are clearly identi- fiable by the presence of a minus sign. Not so for hexadecimal and octal literals. They can take on both positive and negative values. Hex and octal literals are negative if their high-order bit is set. In this program, the number 0xcafebabe is an int constant with its high-order bit set, so it is negative. It is equivalent to the decimal value -889275714.

The addition performed by the program is a mixed-type computation: The left operand is of type long, and the right operand is of type int. To perform the com- putation, Java promotes the int value to a long with a widening primitive conver- sion [JLS 5.1.2] and adds the two long values. Because int is a signed integral type, the conversion performs sign extension: It promotes the negative int value to a numerically equal long value.

The right operand of the addition, 0xcafebabe, is promoted to the long value 0xffffffffcafebabeL. This value is then added to the left operand, which is 0x100000000L. When viewed as an int, the high-order 32 bits of the sign- extended right operand are -1, and the high-order 32 bits of the left operand are 1. Add these two values together and you get 0, which explains the absence of the leading1 digitintheprogram’soutput.Hereishowtheadditionlookswhendone in longhand. (The digits at the top of the addition are carries.)

1111111 0xffffffffcafebabeL

Decimal literals have a nice property that is not shared by hexadecimal or octal literals: Decimal literals are all positive [JLS 3.10.1]. To write a negative decimal constant, you use the unary negation operator (-) in combination with a decimal literal. In this way, you can write any int or long value, whether positive or negative, in decimal form, and negative decimal constants are clearly identi- fiable by the presence of a minus sign. Not so for hexadecimal and octal literals. They can take on both positive and negative values. Hex and octal literals are negative if their high-order bit is set. In this program, the number 0xcafebabe is an int constant with its high-order bit set, so it is negative. It is equivalent to the decimal value -889275714.

The addition performed by the program is a mixed-type computation: The left operand is of type long, and the right operand is of type int. To perform the com- putation, Java promotes the int value to a long with a widening primitive conver- sion [JLS 5.1.2] and adds the two long values. Because int is a signed integral type, the conversion performs sign extension: It promotes the negative int value to a numerically equal long value.

The right operand of the addition, 0xcafebabe, is promoted to the long value 0xffffffffcafebabeL. This value is then added to the left operand, which is 0x100000000L. When viewed as an int, the high-order 32 bits of the sign- extended right operand are -1, and the high-order 32 bits of the left operand are 1. Add these two values together and you get 0, which explains the absence of the leading1 digitintheprogram’soutput.Hereishowtheadditionlookswhendone in longhand. (The digits at the top of the addition are carries.)

1111111 0xffffffffcafebabeL

```
+ 0x0000000100000000L
0x00000000cafebabeL
```

Fixing the problem is as simple as using a long hex literal to represent the right operand. This avoids the damaging sign extension, and the program prints the expected result of 1cafebabe:

Long.toHexString(0x100000000L + 0xcafebabeL));

} }

The lesson of this puzzle is that mixed-type computations can be confusing, more so given that hex and octal literals can take on negative values without an explicit minus sign. To avoid this sort of difficulty, it is generally best to avoid mixed-type computations. For language designers, it is worth considering sup- port for unsigned integral types, which eliminate the possibility of sign extension. One might argue that negative hex and octal literals should be prohibited, but this would likely frustrate programmers, who often use hex literals to represent values whose sign is of no significance.

```
public class JoyOfHex {
public static void main(String[] args) {
```

System.out.println(Long.toHexString(0x100000000L + 0xcafebabeL));

} }

The lesson of this puzzle is that mixed-type computations can be confusing, more so given that hex and octal literals can take on negative values without an explicit minus sign. To avoid this sort of difficulty, it is generally best to avoid mixed-type computations. For language designers, it is worth considering sup- port for unsigned integral types, which eliminate the possibility of sign extension. One might argue that negative hex and octal literals should be prohibited, but this would likely frustrate programmers, who often use hex literals to represent values whose sign is of no significance.

Java Puzzle 6: Multicast

Casts are used to convert a value from one type to another. This program uses three casts in succession. What does it print?

```
public class Multicast {
public static void main(String[] args) {
```

```
System.out.println((int) (char) (byte) -1);
}
```

}

Java Puzzle Solution 6: Multicast

This program is confusing any way you slice it. It starts with the int value -1, then casts the int to a byte, then to a char, and finally back to an int. The first cast nar- rows the value from 32 bits down to 8, the second widens it from 8 bits to 16, and the final cast widens it from 16 bits back to 32. Does the value end up back where it started? If you ran the program, you found that it does not. It prints 65535, but why?

The program’s behavior depends critically on the sign extension behavior of casts. Java uses two’s-complement binary arithmetic, so the int value -1 has all 32 bits set. The cast from int to byte is straightforward. It performs a narrowing primitive conversion [JLS 5.1.3], which simply lops off all but the low-order 8 bits. This leaves a byte value with all 8 bits set, which (still) represents 1.

The cast from byte to char is trickier because byte is a signed type and char unsigned. It is usually possible to convert from one integral type to a wider one while preserving numerical value, but it is impossible to represent a negative byte value as a char. Therefore, the conversion from byte to char is not considered a widening primitive conversion [JLS 5.1.2], but a widening and narrowing primi- tive conversion [JLS 5.1.4]: The byte is converted to an int and the int to a char.

All of this may sound a bit complicated. Luckily, there is a simple rule that describes the sign extension behavior when converting from narrower integral types to wider: Sign extension is performed if the type of the original value is signed; zero extension if it is a char, regardless of the type to which it is being converted. Knowing this rule makes it easy to solve the puzzle.

Because byte is a signed type, sign extension occurs when converting the byte value 1 to a char. The resulting char value has all 16 bits set, so it is equal to 216 1, or 65,535. The cast from char to int is also a widening primitive con- version, so the rule tells us that zero extension is performed rather than sign exten- sion. The resulting int value is 65535, which is just what the program prints.

Although there is a simple rule describing the sign extension behavior of wid- ening primitive conversions between signed and unsigned integral types, it is best not to write programs that depend on it. If you are doing a widening conversion to or from a char, which is the only unsigned integral type, it is best to make your intentions explicit.

If you are converting from a char value c to a wider type and you don’t want sign extension, consider using a bit mask for clarity, even though it isn’t required:

The program’s behavior depends critically on the sign extension behavior of casts. Java uses two’s-complement binary arithmetic, so the int value -1 has all 32 bits set. The cast from int to byte is straightforward. It performs a narrowing primitive conversion [JLS 5.1.3], which simply lops off all but the low-order 8 bits. This leaves a byte value with all 8 bits set, which (still) represents 1.

The cast from byte to char is trickier because byte is a signed type and char unsigned. It is usually possible to convert from one integral type to a wider one while preserving numerical value, but it is impossible to represent a negative byte value as a char. Therefore, the conversion from byte to char is not considered a widening primitive conversion [JLS 5.1.2], but a widening and narrowing primi- tive conversion [JLS 5.1.4]: The byte is converted to an int and the int to a char.

All of this may sound a bit complicated. Luckily, there is a simple rule that describes the sign extension behavior when converting from narrower integral types to wider: Sign extension is performed if the type of the original value is signed; zero extension if it is a char, regardless of the type to which it is being converted. Knowing this rule makes it easy to solve the puzzle.

Because byte is a signed type, sign extension occurs when converting the byte value 1 to a char. The resulting char value has all 16 bits set, so it is equal to 216 1, or 65,535. The cast from char to int is also a widening primitive con- version, so the rule tells us that zero extension is performed rather than sign exten- sion. The resulting int value is 65535, which is just what the program prints.

Although there is a simple rule describing the sign extension behavior of wid- ening primitive conversions between signed and unsigned integral types, it is best not to write programs that depend on it. If you are doing a widening conversion to or from a char, which is the only unsigned integral type, it is best to make your intentions explicit.

If you are converting from a char value c to a wider type and you don’t want sign extension, consider using a bit mask for clarity, even though it isn’t required:

```
int i = c & 0xffff;
```

Puzzle 7: Swap Meat 17 Alternatively, write a comment describing the behavior of the conversion:

char c = (char) (b & 0xff);

If you are converting from a byte to a char and you want sign extension,

write a comment:

Java Puzzle 7: Swap Meat

This program uses the compound assignment operator for exclusive OR. The tech- nique that it illustrates is part of the programming folklore. What does it print?

```
int i = c; // Sign extension is not performed
```

If you are converting from a char value c to a wider integral type and you want sign extension, cast the char to a short, which is the same width as a char but signed. Given the subtlety of this code, you should also write a comment: ```
int i = (short) c; // Cast causes sign extension
```

If you are converting from a byte value b to a char and you don’t want sign extension, you must use a bit mask to suppress it. This is a common idiom, so no comment is necessary: char c = (char) (b & 0xff);

If you are converting from a byte to a char and you want sign extension,

write a comment:

```
char c = (char) b; // Sign extension is performed
```

The lesson is simple: If you can’t tell what a program does by looking at it, it probably doesn’t do what you want. Strive for clarity. Although a simple rule describes the sign extension behavior of widening conversions involving signed and unsigned integral types, most programmers don’t know it. If your program depends on it, make your intentions clear. Java Puzzle 7: Swap Meat

This program uses the compound assignment operator for exclusive OR. The tech- nique that it illustrates is part of the programming folklore. What does it print?

```
public class CleverSwap {
public static void main(String[] args) {
```

} }

```
int x = 1984; // (0x7c0)
int y = 2001; // (0x7d1)
x ^= y ^= x ^= y;
System.out.println("x = " + x + "; y = " + y);
```

Java Puzzle Solution 7: Swap Meat

As its name implies, this program is supposed to swap the values of the variables x and y. It you ran it, you found that it fails miserably, printing x = 0; y = 1984.

The obvious way to swap two variables is to use a temporary variable:

This idiom was used in the C programming language and from there made its way into C++ but is not guaranteed to work in either of these languages. It is guaranteed not to work in Java. The Java language specification says that operands of operators are evaluated from left to right [JLS 15.7]. To evaluate the expression x ^= expr, the value of x is sampled before expr is evaluated, and the exclusive OR of these two values is assigned to the variable x [JLS 15.26.2]. In the CleverSwap program, the variable x is sampled twice—once for each appearance in the expression—but both samplings occur before any assignments.

The following code snippet describes the behavior of the broken swap idiom in more detail and explains the output that we observed:

The obvious way to swap two variables is to use a temporary variable:

```
int tmp = x;
x = y;
y = tmp;
```

Long ago, when central processing units had few registers, it was discovered that one could avoid the use of a temporary variable by taking advantage of the property of the exclusive OR operator (^) that (x ^ y ^ x) == y: ```
// Swaps variables without a temporary - Don’t do this!
```

```
x = x ^ y;
y = y ^ x;
x = y ^ x;
```

Even back in those days, this technique was seldom justified. Now that CPUs have many registers, it is never justified. Like most “clever” code, it is far less clear than its naive counterpart and far slower. Still, some programmers persist in using it. Worse, they complicate matters by using the idiom illustrated in this puz- zle, which combines the three exclusive OR operations into a single statement. This idiom was used in the C programming language and from there made its way into C++ but is not guaranteed to work in either of these languages. It is guaranteed not to work in Java. The Java language specification says that operands of operators are evaluated from left to right [JLS 15.7]. To evaluate the expression x ^= expr, the value of x is sampled before expr is evaluated, and the exclusive OR of these two values is assigned to the variable x [JLS 15.26.2]. In the CleverSwap program, the variable x is sampled twice—once for each appearance in the expression—but both samplings occur before any assignments.

The following code snippet describes the behavior of the broken swap idiom in more detail and explains the output that we observed:

```
// The actual behavior of x ^= y ^= x ^= y in Java
```

```
int tmp1 = x; // First appearance of x in the expression
int tmp2 = y; // First appearance of y
int tmp3 = x ^ y; // Compute x ^ y
```

```
x = tmp3;
y = tmp2 ^ tmp3;
x = tmp1 ^ y;
```

// Last assignment: Store x ^ y in x

// 2nd assignment: Store original x value in y // First assignment: Store 0 in x

// 2nd assignment: Store original x value in y // First assignment: Store 0 in x

In C and C++, the order of expression evaluation is not specified. When com- piling the expression x ^= expr, many C and C++ compilers sample the value of x after evaluating expr, which makes the idiom work. Although it may work, it runs afoul of the C/C++ rule that you must not modify a variable repeatedly between successive sequence points [ISO-C]. Therefore, the behavior of this idiom is unde- fined even in C and C++.

For what it’s worth, it is possible to write a Java expression that swaps the contents of two variables without using a temporary. It is both ugly and useless:

Language designers might consider prohibiting multiple assignments to the same variable in one expression, but it would not be feasible to enforce this prohi- bition in the general case, because of aliasing. For example, consider the expres- sion x = a[i]++ - a[j]++. Does it increment the same variable twice? That depends on the values of i and j at the time the expression is evaluated, and there is no way for the compiler to determine this in general.

Java Puzzle 8: Dos Equis

This puzzle tests your knowledge of the conditional operator, better known as the “question mark colon operator.” What does the following program print?

For what it’s worth, it is possible to write a Java expression that swaps the contents of two variables without using a temporary. It is both ugly and useless:

```
// Rube Goldberg would approve, but don’t ever do this!
```

```
y = (x ^= (y ^= x)) ^ y;
```

The lesson is simple: Do not assign to the same variable more than once in a single expression. Expressions containing multiple assignments to the same variable are confusing and seldom do what you want. Even expressions that assign to multiple variables are suspect. More generally, avoid clever programming tricks. They are bug-prone, difficult to maintain, and often run more slowly than the straightforward code they replace [EJ Item 37]. Language designers might consider prohibiting multiple assignments to the same variable in one expression, but it would not be feasible to enforce this prohi- bition in the general case, because of aliasing. For example, consider the expres- sion x = a[i]++ - a[j]++. Does it increment the same variable twice? That depends on the values of i and j at the time the expression is evaluated, and there is no way for the compiler to determine this in general.

Java Puzzle 8: Dos Equis

This puzzle tests your knowledge of the conditional operator, better known as the “question mark colon operator.” What does the following program print?

```
public class DosEquis {
public static void main(String[] args) {
```

} }

```
char x = ’X’;
int i = 0;
System.out.print(true ? x : 0);
System.out.print(false ? i : x);
```

Puzzle 8: Dos Equis 19

Java Puzzle Solution 8: Dos Equis

The program consists of two variable declarations and two print statements. The first print statement evaluates the conditional expression (true ? x : 0) and prints the result. The result is the value of the char variable x, which is ’X’. The second print statement evaluates the conditional expression (false ? i : x) and prints the result. Again the result is the value of x, which is still ’X’, so the pro- gram ought to print XX. If you ran the program, however, you found that it prints X88. This behavior seems strange. The first print statement prints X and the sec- ond prints 88. What accounts for their different behavior?

The answer lies in a dark corner of the specification for the conditional opera- tor [JLS 15.25]. Note that the types of the second and third operands are different from each other in both of the conditional expressions: x is of type char, whereas 0 and i are both of type int. As mentioned in the solution to Puzzle 5, mixed- type computation can be confusing. Nowhere is this more apparent than in conditional expressions. You might think that the result types of the two condi- tional expressions in this program would be identical, as their operand types are identical, though reversed, but it isn’t so.

The rules for determining the result type of a conditional expression are too long and complex to reproduce in their entirety, but here are three key points.

The answer lies in a dark corner of the specification for the conditional opera- tor [JLS 15.25]. Note that the types of the second and third operands are different from each other in both of the conditional expressions: x is of type char, whereas 0 and i are both of type int. As mentioned in the solution to Puzzle 5, mixed- type computation can be confusing. Nowhere is this more apparent than in conditional expressions. You might think that the result types of the two condi- tional expressions in this program would be identical, as their operand types are identical, though reversed, but it isn’t so.

The rules for determining the result type of a conditional expression are too long and complex to reproduce in their entirety, but here are three key points.

- If the second and third operands have the same type, that is the type of the con- ditional expression. In other words, you can avoid the whole mess by steering clear of mixed-type computation.

- If one of the operands is of type T where T is byte, short, or char and the other operand is a constant expression of type int whose value is representable in type T, the type of the conditional expression is T.

- Otherwise, binary numeric promotion is applied to the operand types, and the type of the conditional expression is the promoted type of the second and third operands.

Points 2 and 3 are the key to this puzzle. In both of the two conditional expres-

the first expression and its return type is char. Point 3 applies to the second condi- tional expression, and its return type is the result of applying binary numeric pro- motion to int and char, which is int [JLS 5.6.2].

The type of the conditional expression determines which overloading of the print method is invoked. For the first expression, PrintStream.print(char) is invoked; for the second, PrintStream.print(int). The former overloading prints the value of the variable x as a Unicode character (X), whereas the latter prints it as a decimal integer (88). The mystery is solved.

Putting the final modifier on the declaration for i would turn i into a con- stant expression, causing the program to print XX, but it would still be confusing. To eliminate the confusion, it is best to change the type of i from int to char, avoiding the mixed-type computation.

In summary, it is generally best to use the same type for the second and third operands in conditional expressions. Otherwise, you and the readers of your program must have a thorough understanding of the complex specification for the behavior of these expressions.

For language designers, perhaps it is possible to design a conditional operator that sacrifices some flexibility for increased simplicity. For example, it might be reasonable to demand that the second and third operands be of the same type. Alternatively, the conditional operator could be defined without special treatment for constants. To make these alternatives more palatable to programmers, a syntax could be provided for expressing literals of all primitive types. This may be a good idea in its own right, as it adds to the consistency and completeness of the lan- guage and reduces the need for casts.

Java Puzzle 9: Tweedledum

Now it’s your turn to write some code. On the bright side, you have to write only two lines for this puzzle and two lines for the next. How hard could that be? Pro- vide declarations for the variables x and i such that this is a legal statement:

x += i;

but this is not:

The type of the conditional expression determines which overloading of the print method is invoked. For the first expression, PrintStream.print(char) is invoked; for the second, PrintStream.print(int). The former overloading prints the value of the variable x as a Unicode character (X), whereas the latter prints it as a decimal integer (88). The mystery is solved.

Putting the final modifier on the declaration for i would turn i into a con- stant expression, causing the program to print XX, but it would still be confusing. To eliminate the confusion, it is best to change the type of i from int to char, avoiding the mixed-type computation.

In summary, it is generally best to use the same type for the second and third operands in conditional expressions. Otherwise, you and the readers of your program must have a thorough understanding of the complex specification for the behavior of these expressions.

For language designers, perhaps it is possible to design a conditional operator that sacrifices some flexibility for increased simplicity. For example, it might be reasonable to demand that the second and third operands be of the same type. Alternatively, the conditional operator could be defined without special treatment for constants. To make these alternatives more palatable to programmers, a syntax could be provided for expressing literals of all primitive types. This may be a good idea in its own right, as it adds to the consistency and completeness of the lan- guage and reduces the need for casts.

Java Puzzle 9: Tweedledum

Now it’s your turn to write some code. On the bright side, you have to write only two lines for this puzzle and two lines for the next. How hard could that be? Pro- vide declarations for the variables x and i such that this is a legal statement:

x += i;

but this is not:

Puzzle 9: Tweedledum 21

x = x + i;

Java Puzzle Solution 9: Tweedledum

Many programmers think that the first statement in this puzzle (x += i) is simply a shorthand for the second (x = x + i). This isn’t quite true. Both of these statements are assignment expressions [JLS 15.26]. The second statement uses the simple assignment operator (=), whereas the first uses a compound assignment operator. (The compound assignment operators are +=, -=, *=, /=, %=, <<=, >>=, >>>=, &=, ^=, and |=.) The Java language specification says that the compound assignment E1 op= E2 is equivalent to the simple assignment E1 = (T) ((E1) op (E2)), where T is the type of E1, except that E1 is evaluated only once [JLS 15.26.2].

In other words, compound assignment expressions automatically cast the result of the computation they perform to the type of the variable on their left-hand side. If the type of the result is identical to the type of the variable, the cast has no effect. If, however, the type of the result is wider than that of the vari- able, the compound assignment operator performs a silent narrowing primitive conversion [JLS 5.1.3]. Attempting to perform the equivalent simple assignment would generate a compilation error, with good reason.

To make this concrete and to provide a solution to the puzzle, suppose that we precede the puzzle’s two assignment expressions with these declarations:

The corresponding simple assignment is illegal because it attempts to assign an int value to a short variable, which requires an explicit cast:

In other words, compound assignment expressions automatically cast the result of the computation they perform to the type of the variable on their left-hand side. If the type of the result is identical to the type of the variable, the cast has no effect. If, however, the type of the result is wider than that of the vari- able, the compound assignment operator performs a silent narrowing primitive conversion [JLS 5.1.3]. Attempting to perform the equivalent simple assignment would generate a compilation error, with good reason.

To make this concrete and to provide a solution to the puzzle, suppose that we precede the puzzle’s two assignment expressions with these declarations:

```
short x = 0;
int i = 123456;
```

The compound assignment compiles without error: ```
x += i; // Contains a hidden cast!
```

You might expect the value of x to be 123,456 after this statement executes, but it isn’t; it’s 7,616. The int value 123456 is too big to fit in a short. The automati- cally generated cast silently lops off the two high-order bytes of the int value, which is probably not what you want. The corresponding simple assignment is illegal because it attempts to assign an int value to a short variable, which requires an explicit cast:

```
x = x + i; // Won’t compile - "possible loss of precision"
```

It should be apparent that compound assignment expressions can be danger- ous. To avoid unpleasant surprises, do not use compound assignment operators on variables of type byte, short, or char. When using compound assignment
operators on variables of type int, ensure that the expression on the right-hand side is not of type long, float, or double. When using compound assignment operators on variables of type float, ensure that the expression on the right-hand side is not of type double. These rules are sufficient to prevent the compiler from generating dangerous narrowing casts.

In summary, compound assignment operators silently generate a cast. If the type of the result of the computation is wider than that of the variable, the gener- ated cast is a dangerous narrowing cast. Such casts can silently discard precision or magnitude. For language designers, it is probably a mistake for compound assignment operators to generate invisible casts; compound assignments where the variable has a narrower type than the result of the computation should proba- bly be illegal.

In summary, compound assignment operators silently generate a cast. If the type of the result of the computation is wider than that of the variable, the gener- ated cast is a dangerous narrowing cast. Such casts can silently discard precision or magnitude. For language designers, it is probably a mistake for compound assignment operators to generate invisible casts; compound assignments where the variable has a narrower type than the result of the computation should proba- bly be illegal.

Java Puzzle 10: Tweedledee

Contrariwise, provide declarations for the variables x and i such that this is a legal statement:

x = x + i;

but this is not:

x += i;

At first glance, this puzzle might appear to be the same as the previous one. Rest assured, it’s different. The two puzzles are opposite in terms of which state- ment must be legal and which must be illegal.

x = x + i;

but this is not:

x += i;

At first glance, this puzzle might appear to be the same as the previous one. Rest assured, it’s different. The two puzzles are opposite in terms of which state- ment must be legal and which must be illegal.

Java Puzzle Solution 10: Tweedledee

Like the previous puzzle, this one depends on the details of the specification for compound assignment operators. That is where the similarity ends. Based on the previous puzzle, you might think that compound assignment operators are less restrictive than the simple assignment operator. This is generally true, but the sim- ple assignment operator is more permissive in one area.

Compound assignment operators require both operands to be primitives, such as int, or boxed primitives, such as Integer, with one exception: The += operator allows its right-hand operand to be of any type if the variable on the left-hand side is of type String, in which case the operator performs string concatenation [JLS 15.26.2]. The simple assignment operator (=) is much less picky when it comes to allowing object reference types on the left-hand side: You can use them to your heart’s content so long as the expression on the right-hand side is assign- ment compatible with the variable on the left [JLS 5.2].

You can exploit this difference to solve the puzzle. To perform string concate- nation with the += operator, you must declare the variable on its left-hand side to be of type String. Using the simple assignment operator, the results of a string concatenation can be stored in a variable of type Object.

To make this concrete and to provide a solution to the puzzle, suppose that we precede the puzzle’s two assignment expressions with these declarations:

x = x + i;

The compound assignment is illegal because the left-hand side has an object refer- ence type other than String:

x += i;

This puzzle has little in the way of a lesson for programmers. For language designers, the compound assignment operator for addition could allow the left- hand side to be of type Object if the right-hand side were of type String. This change would eliminate the counterintuitive behavior illustrated by this puzzle.

#
Tags:

Compound assignment operators require both operands to be primitives, such as int, or boxed primitives, such as Integer, with one exception: The += operator allows its right-hand operand to be of any type if the variable on the left-hand side is of type String, in which case the operator performs string concatenation [JLS 15.26.2]. The simple assignment operator (=) is much less picky when it comes to allowing object reference types on the left-hand side: You can use them to your heart’s content so long as the expression on the right-hand side is assign- ment compatible with the variable on the left [JLS 5.2].

You can exploit this difference to solve the puzzle. To perform string concate- nation with the += operator, you must declare the variable on its left-hand side to be of type String. Using the simple assignment operator, the results of a string concatenation can be stored in a variable of type Object.

To make this concrete and to provide a solution to the puzzle, suppose that we precede the puzzle’s two assignment expressions with these declarations:

```
Object x = "Buy ";
String i = "Effective Java!";
```

The simple assignment is legal because x + i is of type String, and String is assignment compatible with Object: x = x + i;

The compound assignment is illegal because the left-hand side has an object refer- ence type other than String:

x += i;

This puzzle has little in the way of a lesson for programmers. For language designers, the compound assignment operator for addition could allow the left- hand side to be of type Object if the right-hand side were of type String. This change would eliminate the counterintuitive behavior illustrated by this puzzle.

## Comments

## Post a Comment