How to detect overflow of "unsigned" long multiplication in Java?

Question

Java does not have "unsigned" long values, of course, but sometimes signed long values are effectively treated as unsigned long values (the result of System.nanoTime(), for example). In this sense, arithmetic overflow doesn't so much mean overflow of a value as much as it means overflow of the 64-bit representation. Examples:

Long.MAX_VALUE * 2L  // overflows the signed product but not the unsigned product
Long.MAX_VALUE * 4L  // overflows the signed product and the unsigned product
-1L * 2L             // overflows the unsigned product but not the signed product

Testing whether a multiplication overflows seems to be somewhat complicated, since the sign-iness of the operations gets in the way. It may be helpful to note that any negative value multiplied by any value other than 0 or 1 will overflow the unsigned product, since the highest bit of the negative value is set.

What would be the best way to determine whether the product of two "unsigned" long values—which are really signed long values—would overflow the 64-bit representation? Using instances of BigInteger is an obvious solution, and I've derived a convoluted test involving only primitive operations, but I feel like I'm missing something obvious.

Answer 1

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.