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.
actually the ternary operator DOES result in a branch, it’s ust not based on an “IF” in the language, but for the compile/JVM, it’s same. No matter, this is still an elegant solution. I HATE C/C++, but times like this particular one make me think “macro.” Still I’ll take java anyday over C/C++
Of course it does. But this doesn’t use a ternary operator.
> (there’s probably a nicer way to see that it works, but I’m blanking on what it is)
A truth table?
A truth table is just a way of laying out the answers. It doesn’t omit the burden of actually proving each case, which is what I did there.
Here’s another way of reading it:
“(i < 0) ^ (j < 0)” reads as “i and j have different signs”.
So the whole thing reads “i less than j, xor i and j have different signs”, so
– either i j, and i and j have differing signs
(Oh dear. Less-than/greater-than munging obliterated the fully spelled-out version at the end of the previous comment.)
So it returns true if “i >= j”?
I know I’m about 6 years late to the discussion, but some of the posters above have missed the crucial point of the post, so I want to correct it for posterity. The point is not that the comparison can be simplified to less than/greater than (as Mr. Garnock-Jones says), it’s that in Java/Scala/JVM technologies negative numbers are represented in 2’s complement. This means that -1 == 0xFFFFFFFF. In an unsigned comparison 0xFFFFFFFF > 0x7FFFFFFF is true, but in JVM technologies, this comparison would evaluate to false (try it). I’ve found this posting useful and integrated it into a bit of Java code to compute magic numbers for signed division (from Hacker’s Delight).
Pingback: Unsigned comparisons in Java | Optimi