SSerguey Asael Shinder
Java coding notes: the JVM, and writing software that lasts

Serguey Asael Shinder: A packed int sorts with Integer.compare only while the sign bit stays free

· by Serguey Asael Shinder / Serguey Shinder

Packing several small fields into one int is an old trick, and this week's Valhalla ticker example on Inside Java uses it well: five six-bit character codes, highest slot first, so that comparing the integers compares the symbols. The article points out the condition that makes this work. The codes occupy 30 bits, the top two bits are always zero, so every packed value is non-negative and a plain Integer.compare gives string order.

That condition is easy to break without noticing. The same article, in its section on further improvements, observes that the two spare bits could hold a length. Spend the top one, or pack four 8-bit fields into all 32 bits, and some keys become negative numbers.

The javadoc of Integer.compare(int, int) is explicit that it compares two int values numerically, the same as Integer.valueOf(x).compareTo(Integer.valueOf(y)). Numerically means signed. A key whose top bit is set is less than every key whose top bit is clear:

int high = 0x80000000; // top field = 0x80
int low  = 0x7FFFFFFF; // top field = 0x7F
Integer.compare(high, low);          // negative: high sorts first
Integer.compareUnsigned(high, low);  // positive: high sorts last
Serguey Asael Shinder: A packed int sorts with Integer.compare only while the sign bit stays free
A packed int sorts with Integer.compare only while the sign bit stays free — Serguey Asael Shinder

If the packing was designed so that the first field decides the order, the first line is wrong and nothing warns you. Small test data, where the top field never reaches 0x80, sorts correctly; real data does not.

The fix is in the same class. Integer.compareUnsigned(int, int), available since Java 8, compares two int values numerically treating the values as unsigned, and returns a negative value, zero or a positive value accordingly. It reads the 32 bits as the big-endian field layout you packed. Long.compareUnsigned does the same for 64-bit keys.

Two habits follow. Write the comparator to match the packing, unsigned unless you have proved the sign bit is never used, and say so in a comment next to the bit layout. And when you print such keys for debugging, use Integer.toUnsignedString or hex, because the signed decimal of a packed key is a number that means nothing.

The ticker class is safe as written, because its author reserved the sign bit by construction. The point is that the safety lives in a property of the encoding, not in the comparator, and the next person to widen the encoding may not know that.