Edit
As promised in one of my comments to original post I will now post strict and correct solution. It has less divisions that Nathan's own formula (for those interested see last code line in his answer), but it has additional branching, so I am not sure it will be better performance-wise.
And, alas, it is not one-liner. Here it is:
static boolean unsignedMultiplyOverflows(final long a, final long b) {
if (a == 0 || b == 0) {
return false;
}
// now proceed with non-zero input
// we branch based upon parity of a and b
final long aHalf = a >>> 1;
final long bHalf = b >>> 1;
final byte aLastBit = (byte) (a & 1);
final byte bLastBit = (byte) (b & 1);
if (aLastBit == 0) { // a = 2 * aHalf, meaning unsigned representation of a
return Long.MAX_VALUE / b < aHalf;
} else if (bLastBit == 0) { // b = 2 * bHalf
return Long.MAX_VALUE / a < bHalf; // symmetrical to previous case
} else { // a = 2 * aHalf + 1; b = 2 * bHalf + 1
return (Long.MAX_VALUE - bHalf) / b < aHalf;
}
}
The formal proof is based on investigation of 2 cases, 1. At least one of multipliers is even, and 2. a
,b
both odd. I could add it if anyone is interested.
I have unit-tested it on full range of chars : 0 ~ 0xffff for overflow of 16-bit numbers, and also on some random long
input, comparing results with both Nathan's method and BigInteger
solution as a reference.
Hope that helps.