Puzzle 33: Looper Meets the Wolfman

Provide a declaration for i that turns this loop into an infinite loop. This one doesn't require the use of any release 5.0 features:

while (i != 0 && i == -i) {

}

Solution 33: Looper Meets the Wolfman

Yet another puzzling looper. In the boolean expression (i != 0 && i == -i), the unary minus operator is applied to i, which implies that its type must be numeric: It is illegal to apply the unary minus operator to a non-numeric operand. Therefore, we are looking for a nonzero numeric value that is equal to its own negation. NaN does not satisfy this property, as it is not equal to any value, so i must represent an actual number. Surely there is no number with this property?

Well, there is no real number with this property, but none of Java's numeric types model the real numbers perfectly. Floating-point values are represented with a sign bit; a significand, informally known as the mantissa; and an exponent. No floating-point value other than 0 is equal to itself with the sign bit flipped, so the type of i must be integral.

The signed integral types use two's-complement arithmetic: To negate a value, you flip every bit and add 1 to the result [JLS 15.15.4]. One big advantage of two's-complement arithmetic is that there is a unique representation for 0. If you negate the int value 0, you get 0xffffffff + 1, which is 0. There is, however, a corresponding disadvantage. There exist an even number of int values—2³² to be precise—and one of these values is used to represent 0. That leaves an odd number of int values to represent positive and negative integers, which means that there must be a different number of positive and negative int values. This in turn implies that there is at least one int value whose negation cannot be correctly represented as an int value.

In fact, there is exactly one such int value, and it is Integer.MIN_VALUE, or -2³¹. Its hexadecimal representation is 0x8000000. The sign bit is 1, and all the other bits are 0. If we negate this value, we get 0x7fffffff + 1, which is 0x8000000, or Integer.MIN_VALUE! In other words, Integer.MIN_VALUE is its own negation, as is Long.MIN_VALUE. Negating either of these values causes an overflow, but Java ignores overflows in integer computations. The results are well defined, even if they are not always what you want them to be.

This declaration will make the boolean expression (i != 0 && i == -i) evaluate to true, causing the loop to spin indefinitely:

int i = Integer.MIN_VALUE;

So will this one:

long i = Long.MIN_VALUE;

In case you're familiar with modular arithmetic, it's worth pointing out that this puzzle can be solved algebraically. Java's int arithmetic is actually arithmetic mod 2³², so the puzzle requires a nonzero solution to this linear congruence:

i –i (mod 2³²)

Adding i to both sides, we get:

2i 0 (mod 2³²)

The nonzero solution to this congruence is i = 2³¹. Although this value is not representable as an int, it is congruent to -2³¹, which is Integer.MIN_VALUE.

In summary, Java uses two's-complement arithmetic, which is asymmetric. The signed integral types (int, long, byte, and short) each have one more negative value than positive, which is always the minimum value representable in the type. Negating Integer.MIN_VALUE doesn't change its value, and the same holds true for Long.MIN_VALUE. Negating Short.MIN_VALUE and casting the resulting int value back to a short returns the original value (Short.MIN_VALUE). A similar result holds for Byte.MIN_VALUE. More generally, watch out for overflow: Like the Wolfman, it's a killer.

The lesson for language designers is the same as in Puzzle 26. Consider providing linguistic support for some form of integer arithmetic where overflow does not happen silently.