Java (and consequently Scala) lack unsigned integer types. Most of the time this isn’t an issue – the majority of the operations you’re likely to care about (addition, subtraction, bitwise operations) work the same regardless of whether you treat the integer as unsigned. There are a few cases where it is a pain though – one that bit me in the context of the work I’ve been doing on and off with Java classfiles is that converting between types of different size. The other one that’s an issue is comparison – integer comparison is signed in Java and there are no operations for doing the unsigned compare.

One way to fix this is to delegate to a solution to the previous problem: Bump the integers up to a type one size up in an unsigned way so that they get converted to positive values, do a comparison on there. This works fine for the smaller values, but if you were to do this with a long you’d have to upgrade to a BigInt, which is a bit sad. I’d previously been doing it this way but earlier when I needed to do unsigned comparisons on longs I decided to look for a better route. (Full disclosure: Actually what happened is I converted some code using ints to code using long and suddenly all my unit tests broke. At that point I discovered that I’d still been trying to do an unsigned comparison using the code for doing it for integers).

Anyway, I popped into ##java to see if anyone there had any ideas for how to do it. Totally counter to form, ##java was actually incredibly useful. The best solution came from someone who went by Tamutnefret and is as follows:

  def unsignedCompare(i : Long, j : Long) = (i < j) ^ (i < 0) ^ (j < 0)

Which is really neat and avoids doing any branching.

Let’s see why this works. We’ll break it down by cases on i (there’s probably a nicer way to see that it works, but I’m blanking on what it is).

Suppose i = 0. This becomes (0 < j) ^ false ^ (j < 0), which is (0 < j) ^ (j < 0), or j != 0. Which is correct, as the only unsigned integer not > 0 is 0.

Suppose now i < 0. This becomes (i < j) ^ true ^ (j < 0).
If (j < 0) this becomes i < j, as x ^ true ^ true = x ^ false = x. If j >= 0 then we certainly have i < j, so we get true ^ true ^ false = false, which is again correct: In unsigned comparison any negative number is greater than any non-negative one. The case i > 0 follows similarily (the standard mathematician’s weasel words).

Anyway, the explanation of why is boring. It takes less time to convince yourself of its truth than it did to read that. :-) But the point is that it’s a cute, useful formula which I’d not previously encountered so I thought I’d record it here.