The comparator that subtracts
A hard Java puzzle in the numeric overflow and precision family. One line below contains a real bug. Try to spot it first, then read why it fails and how to fix it.
Highlighted: line 9. Play this one as a puzzle without the answer.
What is wrong
Subtracting two ints can overflow: 1000000 - Integer.MIN_VALUE wraps to a negative number, so the comparator claims that high is smaller than low and the sort order is wrong. It also violates the comparator contract, which can make TimSort throw.
The fix
How to avoid it next time
Never write comparators with subtraction. Use Integer.compare or Comparator.comparingInt.
Want the background? Read Comparable and Comparator in the Java concepts library.
About numeric overflow and precision
Java integers wrap around silently when they exceed their range, with no exception. int and long arithmetic, integer division and implicit narrowing casts all produce wrong numbers that look plausible.
In code review: Look at the type of every operand, not the type of the variable receiving the result. Multiplication of two ints happens in int even when assigned to a long. Use Math.addExact, long literals and BigDecimal for money.
More puzzles in this family
Frequently asked questions
What is the bug in "The comparator that subtracts"?
Subtracting two ints can overflow: 1000000 - Integer.MIN_VALUE wraps to a negative number, so the comparator claims that high is smaller than low and the sort order is wrong. It also violates the comparator contract, which can make TimSort throw. The faulty line is line 9: tasks.sort((a, b) -> a.priority() - b.priority());
How do I fix it?
Replace it with: tasks.sort(Comparator.comparingInt(Task::priority));. Never write comparators with subtraction. Use Integer.compare or Comparator.comparingInt.
How do I catch numeric overflow and precision in code review?
Look at the type of every operand, not the type of the variable receiving the result. Multiplication of two ints happens in int even when assigned to a long. Use Math.addExact, long literals and BigDecimal for money.
Is there a new puzzle every day?
Yes. The daily Spot the Bug puzzle picks one of these snippets for each UTC day, with the difficulty set by the weekday. Your streak is stored only in your browser.