Internet Problem Solving Contest

IPSC 2008

Solution to Problem C – Comparison Mysteries

Minus x equals x

For the easy data set, your task was to find a non-zero number that is equal to its negation.

The key trick is that for signed integer data types the set of possible values is asymetric. For example, the smallest possible int is -231 and the largest is 231 - 1. This leaves us with 231 - 1 pairs (x,-x), and two special values: 0 and -231.

The negation of -231 would be 231. However, this does not fit into an int. More precisely, 231 is one larger than the largest allowed value, and this overflows to the smallest allowed value: -231 again.

(Essentially, all computations with b-bit integers are done modulo 2b in the sense that results that differ by a multiple of 2b will, due to overflow, be represented by the same bit pattern.)

Note that when comparing less-than-32 bit integer variables in Java, they get promoted to ints. This causes our solution to work only for ints and longs.

The two solutions to this problem are: int x = -2147483648 and long x = -9223372036854775808.

Equality is not transitive

If comparing variables of different types, they are usually first both promoted to the larger of those two types. For example, when comparing a short and an int, the short is cast to an int, and then they are compared.

The problem is that sometimes there is no good choice – the two types can have incomparable ranges of possible values. In that case, the language designers have to pick one of them.

For example, this often happens when comparing an integer data type to a floating point one.

In Java and many other languages, floating point types get precedence. To quote the reference: If either operand is of type double, the other is converted to double. Otherwise, if either operand is of type float, the other is converted to float.

The problem here is that a long is a 64-bit integer, whereas a double only has 53 bits to store the digits. Thus there are values that can be stored in a long but can not be represented exactly in a double. For the same reason, we may lose precision when converting an int into a float.

This can cause two different ints to be converted into the same float. For example, the ints 1234567890 and 1234567891 will.

We can use this to construct a solution to the hard problem. One possible solution is: int x = 1234567890, float y = 1234567890, and int z = 1234567891. Both for x==y and y==z the int is converted to a float, and thanks to the precision loss equality holds. However, with x==z we are comparing two ints, and find that they differ.