GotchaDifficulty: Advanced1 min

Integer Overflow in Comparators: Why Subtraction Is a Bug

A comparator that worked for years misorders the one dataset with a huge and a very negative value.

Writing a comparator by subtracting one value from the other relies on the sign of the difference, and subtracting two int values can overflow: the true result does not fit in an int, wraps round, and comes out with the wrong sign. The sort then puts the two elements in the wrong order.

A comparator that has sorted correctly for years produces one wrong ordering, on a dataset with a very large value and a very negative one in it:

java

(a, b) -> a.score() - b.score()

Two billion minus negative two billion is four billion, which does not fit in an int, whose largest value is about 2.1 billion:

java

int big = 2_000_000_000;
int verySmall = -2_000_000_000;

System.out.println(big - verySmall);

text

-294967296

Two billion is the larger score, so a correct comparator returns something positive. This one returns a negative number, so the sort puts the larger score first, and a sort given inconsistent answers produces an order that is wrong in ways that are hard to reproduce.

Use Integer.compare(a, b) or Comparator.comparingInt(...), both of which compare rather than subtract. The same applies to long, where the wrap-around is rarer and just as wrong.

← → move through sections and cards