Java Integer compareTo() - why use comparison vs. subtraction?
JavaOptimizationIntegerComparisonInteger OverflowJava Problem Overview
I've found that java.lang.Integer
implementation of compareTo
method looks as follows:
public int compareTo(Integer anotherInteger) {
int thisVal = this.value;
int anotherVal = anotherInteger.value;
return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
}
The question is why use comparison instead of subtraction:
return thisVal - anotherVal;
Java Solutions
Solution 1 - Java
This is due to integer overflow. When thisVal
is very large and anotherVal
is negative then subtracting the latter from the former yields a result that is bigger than thisVal
which may overflow to the negative range.
Solution 2 - Java
The subtraction "trick" to compare two numerical value is broken!!!
int a = -2000000000;
int b = 2000000000;
System.out.println(a - b);
// prints "294967296"
Here, a < b
, yet a - b
is positive.
DO NOT use this idiom. It doesn't work.
Moreover, even if it does work, it will NOT provide any significant improvement in performance, and may in fact cost readability.
See also
- Java Puzzlers Puzzle 65: A Strange Saga of Suspicious Sort
> This puzzle has several lessons. The most specific is: Do not use a subtraction-based comparator unless you are sure that the difference between values will never be greater than
Integer.MAX_VALUE
. More generally, beware ofint
overflow. Another lesson is that you should avoid "clever" code. Strive to write clear, correct code, and do not optimize it unless it proves necessary.
Solution 3 - Java
Simply speaking, the int
type is not big enough to store the difference between two arbitrary int
values. For example, the difference between 1.5 billion and -1.5 billion is 3.0 billion, but int
cannot hold values greater than 2.1 billion.
Solution 4 - Java
Perhaps it's to avoid overflow / underflow.
Solution 5 - Java
In addition to the overflow thing, you should note that the version with substraction does not give the same results.
- The first compareTo version returns one of three possible values: -1, 0, or 1.
- If you replace the last line with substraction, the result can be any integer value.
If you know there will be no overflow, you could use something like this:
public int compareTo(Integer anotherInteger) {
return sign(this.value - anotherInteger.valuel);
}