Larger Than Life

Larger Than Life

Lest you think that this book is going entirely to the dogs, this puzzle concerns royalty. If the tabloids are to be believed, the King of Rock 'n' Roll is still alive. Not one of his many impersonators but the one true Elvis. This program estimates his current belt size by projecting the trend observed during his public performances. The program uses the idiom Calendar.getInstance().get(Calendar.YEAR), which returns the current calendar year. What does the program print?

public class Elvis {

    public static final Elvis INSTANCE = new Elvis();

    private final int beltSize;

    private static final int CURRENT_YEAR =

        Calendar.getInstance().get(Calendar.YEAR);



    private Elvis() {

        beltSize = CURRENT_YEAR - 1930;

    }



    public int beltSize() {

        return beltSize;

    }



    public static void main(String[] args) {

        System.out.println("Elvis wears a size " +

                           INSTANCE.beltSize() + " belt.");

    }

}

Solution : Larger Than Life

At first glance, this program appears to compute the current year minus 1930. If that were correct, in the year 2006, the program would print Elvis wears a size 76 belt. If you tried running the program, you learned that the tabloids were wrong, proving that you can't believe everything you read in the papers. It prints Elvis wears a size -1930 belt. Perhaps the King has gone on to inhabit an anti-matter universe?

This program suffers a problem caused by a circularity in the order of class initialization . Let's follow it in detail. Initialization of the class Elvis is triggered by the VM's call to its main method. First, static fields are set to their default values . The field INSTANCE is set to null, and CURRENT_YEAR is set to 0. Next, static field initializers are executed in order of appearance. The first static field is INSTANCE. Its value is computed by invoking the Elvis() constructor.

The constructor initializes beltSize to an expression involving the static field CURRENT_YEAR. Normally, reading a static field is one of the things that causes a class to be initialized, but we are already initializing the class Elvis. Recursive initialization attempts are simply ignored . Consequently, the value of CURRENT_YEAR still has its default value of 0. That is why Elvis's belt size turns out to be -1930.

Finally, returning from the constructor to complete the class initialization of Elvis, we initialize the static field CURRENT_YEAR to 2006, assuming you're running the program in 2006. Unfortunately, it is too late for the now correct value of this field to affect the computation of Elvis.INSTANCE.beltSize, which already has the value -1930. This is the value that will be returned by all subsequent calls to Elvis.INSTANCE.beltSize().

This program shows that it is possible to observe a final static field before it is initialized, when it still contains the default value for its type. That is counterintuitive, because we usually think of final fields as constants. Final fields are constants only if the initializing expression is a constant expression .

Problems arising from cycles in class initialization are difficult to diagnose but once diagnosed are usually easy to fix. To fix a class initialization cycle, reorder the static field initializers so that each initializer appears before any initializers that depend on it. In this program, the declaration for CURRENT_YEAR belongs before the declaration for INSTANCE, because the creation of an Elvis instance requires that CURRENT_YEAR be initialized. Once the declaration for CURRENT_YEAR has been moved, Elvis will indeed be larger than life.

Some common design patterns are naturally subject to initialization cycles, notably the Singleton , which is illustrated in this puzzle, and the Service Provider Framework . The Typesafe Enum pattern also causes class initialization cycles. Release 5.0 adds linguistic support for this pattern with enum types. To reduce the likelihood of problems, there are some restrictions on static initializers in enum types .

In summary, be careful of class initialization cycles. The simplest ones involve only a single class, but they can also involve multiple classes. It isn't always wrong to have class initialization cycles, but they may result in constructor invocation before static fields are initialized. Static fields, even final static fields, may be observed with their default value before they are initialized.

In the Loop

In the Loop

The following program counts the number of iterations of a loop and prints the count when the loop terminates. What does it print?

public class InTheLoop {

    public static final int END = Integer.MAX_VALUE;

    public static final int START = END - 100;



    public static void main(String[] args) {

        int count = 0;

        for (int i = START; i <= END; i++)

            count++;

        System.out.println(count);

    }

}

Solution : In the Loop

If you don't look at the program very carefully, you might think that it prints 100; after all, END is 100 more than START. If you look a bit more carefully, you will see that the program doesn't use the typical loop idiom. Most loops continue as long as the loop index is less than the end value, but this one continues as long as the index is less than or equal to the end value. So it prints 101, right? Well, no. If you ran the program, you found that it prints nothing at all. Worse, it keeps running until you kill it. It never gets a chance to print count, because it's stuck in an infinite loop.

The problem is that the loop continues as long as the loop index (i) is less than or equal to Integer.MAX_VALUE, but all int variables are always less than or equal to Integer.MAX_VALUE. It is, after all, defined to be the highest int value in existence. When i gets to Integer.MAX_VALUE and is incremented, it silently wraps around to Integer.MIN_VALUE.

If you need a loop that iterates near the boundaries of the int values, you are better off using a long variable as the loop index. Simply changing the type of the loop index from int to long solves the problem, causing the program to print 101 as expected:

for (long i = START; i <= END; i++)

More generally, the lesson here is that ints are not integers. Whenever you use an integral type, be aware of the boundary conditions. What happens if the value underflows or overflows? Often it is best to use a larger type. (The integral types are byte, char, short, int, and long.)

It is possible to solve this problem without resorting to a long index variable, but it's not pretty:

int i = START;

do {

    count++;

} while (i++ != END);

Given the paramount importance of clarity and simplicity, it is almost always better to use a long index under these circumstances, with perhaps one exception: If you are iterating over all (or nearly all) the int values, it's about twice as fast to stick with an int. Here is an idiom to apply a function f to all four billion int values:

// Apply the function f to all four billion int values

int i = Integer.MIN_VALUE;

do {

    f(i);

} while (i++ != Integer.MAX_VALUE);

The lesson for language designers is : It may be worth considering support for arithmetic that does not overflow silently. Also, it may be worth providing support for loops designed specifically to iterate over ranges of integral values, as many languages do.

A Big Delight in Every Byte

A Big Delight in Every Byte

This program loops through the byte values, looking for a certain value. What does the program print?

public class BigDelight {

    public static void main(String[] args)  {

        for (byte b = Byte.MIN_VALUE; b < Byte.MAX_VALUE; b++) {

            if (b == 0x90)

                System.out.print("Joy!");

        }

    }

}

Solution : A Big Delight in Every Byte

The loop iterates over all the byte values except Byte.MAX_VALUE, looking for Ox90. This value fits in a byte and is not equal to Byte.MAX_VALUE, so you might think that the loop would hit it once and print Joy! on that iteration. Looks can be deceiving. If you ran the program, you found that it prints nothing. What happened?

Simply put, Ox90 is an int constant that is outside the range of byte values. This is counterintuitive because Ox90 is a two-digit hexadecimal literal. Each hex digit takes up 4 bits, so the entire value takes up 8 bits, or 1 byte. The problem is that byte is a signed type. The constant 0x90 is a positive int value of 8 bits with the highest bit set. Legal byte values range from -128 to +127, but the int constant 0x90 is equal to +144.

The comparison of a byte to an int is a mixed-type comparison. If you think of byte values as apples and int values as oranges, the program is comparing apples to oranges. Consider the expression ((byte)0x90 == 0x90). Appearances notwithstanding, it evaluates to false. To compare the byte value (byte)0x90 to the int value 0x90, Java promotes the byte to an int with a widening primitive conversion [JLS 5.1.2] and compares the two int values. Because byte is a signed type, the conversion performs sign extension, promoting negative byte values to numerically equal int values. In this case, the conversion promotes (byte)0x90 to the int value -112, which is unequal to the int value 0x90, or +144.

Mixed-type comparisons are always confusing because the system is forced to promote one operand to match the type of the other. The conversion is invisible and may not yield the results that you expect. There are several ways to avoid mixed-type comparisons. To pursue our fruit metaphor, you can choose to compare apples to apples or oranges to oranges. You can cast the int to a byte, after which you will be comparing one byte value to another:

if (b == (byte)0x90)

    System.out.println("Joy!");

Alternatively, you can convert the byte to an int, suppressing sign extension with a mask, after which you will be comparing one int value to another:

if ((b & 0xff) == 0x90)

    System.out.println("Joy!");

Either of these solutions works, but the best way to avoid this kind of problem is to move the constant value outside the loop and into a constant declaration.

Here is a first attempt:

public class BigDelight {

    private static final byte TARGET = 0x90; // Broken!

    public static void main(String[] args) {

        for (byte b = Byte.MIN_VALUE; b < Byte.MAX_VALUE; b++)

            if (b == TARGET)

                System.out.print("Joy!");

    }

}

Unfortunately, it doesn't compile. The constant declaration is broken, and the compiler will tell you the problem: 0x90 is not a valid value for the type byte. If you fix the declaration as follows, the program will work fine:

private static final byte TARGET = (byte)0x90;

To summarize: Avoid mixed-type comparisons, because they are inherently confusing (The Joy of Hex). To help achieve this goal, use declared constants in place of "magic numbers." You already knew that this was a good idea; it documents the meanings of constants, centralizes their definitions, and eliminates duplicate definitions. Now you know that it also forces you to give each constant a type appropriate for its use, eliminating one source of mixed-type comparisons.

The lesson for language designers is that sign extension of byte values is a common source of bugs and confusion. The masking that is required in order to suppress sign extension clutters programs, making them less readable. Therefore, the byte type should be unsigned. Also, consider providing literals for all primitive types, reducing the need for error-prone type conversions

Tweedledee

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 statement must be legal and which must be illegal.

Solution : 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 simple 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 assignment compatible with the variable on the left [JLS 5.2].

You can exploit this difference to solve the puzzle. To perform string concatenation 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 reference 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.

Tweedledum

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? Provide declarations for the variables x and i such that this is a legal statement:

x += i;

but this is not:

x = x + i;

Solution : 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 variable, 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 automatically 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 dangerous. 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 generated 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 probably be illegal.

Dos Equis

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);

    }

}

Solution : 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 program 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 second prints 88. What accounts for their different behavior?

The answer lies in a dark corner of the specification for the conditional operator [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 The joy of hex, 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 conditional 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.

1. 
   

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

   
   



2. 
   

   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.

   
   



3. 
   

   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 expressions in the program, one operand is of type char and the other is of type int. In both expressions, the value of the int operand is 0, which is representable as a char. Only the int operand in the first expression, however, is constant (0); the int operand in the second expression is variable (i). Therefore, point 2 applies to the first expression and its return type is char. Point 3 applies to the second conditional expression, and its return type is the result of applying binary numeric promotion 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 constant 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 language and reduces the need for casts.

Swap Meat

Swap Meat

This program uses the compound assignment operator for exclusive OR. The technique 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);

    }

}

Solution : 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:

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 puzzle, 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;         // Last assignment: Store x ^ y in x

y = tmp2 ^ tmp3;  // 2nd assignment: Store original x value in y

x = tmp1 ^ y;     // First assignment: Store 0 in x

In C and C++, the order of expression evaluation is not specified. When compiling 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. Therefore, the behavior of this idiom is undefined 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:

// 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 prohibition in the general case, because of aliasing. For example, consider the expression 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.

Multicast

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);

    }

}

Solution : 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 narrows 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 primitive 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 2¹⁶ – 1, or 65,535. The cast from char to int is also a widening primitive conversion, so the rule tells us that zero extension is performed rather than sign extension. 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 widening 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;

Alternatively, write a comment describing the behavior of the conversion:

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.

The Joy of Hex

The Joy of Hex

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));

    }

}

Solution : The Joy of Hex

It seems obvious that the program should print 1cafebabe. After all, that is the sum of the hex numbers 100000000₁₆ and cafebabe₁₆. 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 somehow 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 identifiable 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 computation, Java promotes the int value to a long with a widening primitive conversion [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 leading 1 digit in the program's output. Here is how the addition looks when done 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:

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 support 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.

Elementary

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);

    }

}

Solution : 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.

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 + operator. 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 lowercase 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<String> l = new ArrayList<String>();

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 lowercase 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.

Long Division

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);

    }

}

Solution : 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 microseconds/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 millisecond. 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 primitive 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 factors that are multiplied together are int values. When you multiply two int values, 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 expression 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. Similarly, it isn't always necessary to use a long as the first value in a product, but it is 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:

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 likelihood 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

The Last Laugh

What does the following program print?

public class LastLaugh {

    public static void main(String args[]) {

        System.out.print("H" + "a");

        System.out.print('H' + 'a');

    }

}

Solution : The Last Laugh

If you are like most people, you thought that the program would print HaHa. It looks as though it concatenates H to a in two ways, but looks can be deceiving. If you ran the program, you found that it prints Ha169. Now why would it do a thing like that?

As expected, the first call to System.out.print prints Ha: Its argument is the expression "H" + "a", which performs the obvious string concatenation. The second call to System.out.print is another story. Its argument is the expression 'H' + 'a'. The problem is that 'H' and 'a' are char literals. Because neither operand is of type String, the + operator performs addition rather than string concatenation.

The compiler evaluates the constant expression 'H' + 'a' by promoting each of the char-valued operands ('H' and 'a') to int values through a process known as widening primitive conversion [JLS 5.1.2, 5.6.2]. Widening primitive conversion of a char to an int zero extends the 16-bit char value to fill the 32-bit int. In the case of 'H', the char value is 72 and in the case of 'a', it is 97, so the expression 'H' + 'a' is equivalent to the int constant 72 + 97, or 169.

From a linguistic standpoint, the resemblance between char values and strings is illusory. As far as the language is concerned, a char is an unsigned 16-bit primitive integer—nothing more. Not so for the libraries. They contain many methods that take char arguments and treat them as Unicode characters.

So how do you concatenate characters? You could use the libraries. For example, you could use a string buffer:

StringBuffer sb = new StringBuffer();

sb.append('H');

sb.append('a');

System.out.println(sb);

This works, but it's ugly. There are ways to avoid the verbosity of this approach. You can force the + operator to perform string concatenation rather than addition by ensuring that at least one of its operands is a string. The common idiom is to begin a sequence of concatenations with the empty string (""), as follows:

System.out.print("" + 'H' + 'a');

This idiom ensures that subexpressions are converted to strings. Although useful it is a bit ungainly and can lead to some confusion itself.

Can you guess what the following statement prints? If you aren't sure, try it:

System.out.println("2 + 2 = " + 2+2);

As of release 5.0, you also have the option of using the printf facility:

System.out.printf("%c%c", 'H', 'a');

In summary, use the string concatenation operator with care. The + operator performs string concatenation if and only if at least one of its operands is of type String; otherwise, it performs addition. If none of the values to be concatenated are strings, you have several choices: prepend the empty string; convert the first value to a string explicitly, using String.valueOf; use a string buffer; or if you are using release 5.0, use the printf facility.

This puzzle also contains a lesson for language designers. Operator overloading, even to the limited extent that it is supported in Java, can be confusing. It may have been a mistake to overload the + operator for string concatenation.

Problem of Change

Problem of Change

public class Change {

    public static void main(String args[]) {

        System.out.println(2.00 - 1.10);

    }

}

Solution : Problem of 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 documentation for Double.toString [Java-API], you know that the program prints the shortest decimal fraction sufficient to distinguish the double value from its nearest 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:

// 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 underlying problem: It still uses double arithmetic, which is binary floating-point. Floating-point arithmetic provides good approximations over a wide range of values but does not generally yield exact results. Binary floating-point is particularly 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 representing 0.1000000000000000055511151231257827021181583404541015625. Using BigDecimal correctly, the program prints the expected result of 0.90:

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 designers, 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.