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.

Answer 2

Given two signed long values that we are pretending to be unsigned long values, here is how to determine whether the unsigned product would overflow, using only signed primitive operations (please forgive the pedantry):

boolean unsignedMultiplyOverflows(final long a, final long b) {
    if ((a == 0L) || (b == 0L)) {
        // Unsigned overflow of a * b will not occur, since the result would be 0.
        return false;
    }
    if ((a == 1L) || (b == 1L)) {
        // Unsigned overflow of a * b will not occur, since the result would be a or b.
        return false;
    }
    if ((a < 0L) || (b < 0L)) {
        // Unsigned overflow of a * b will occur, since the highest bit of one argument is set, and a bit higher than the lowest bit of the other argument is set.
        return true;
    }
    /*
     * 1 < a <= Long.MAX_VALUE
     * 1 < b <= Long.MAX_VALUE
     *
     * Let n == Long.SIZE (> 2), the number of bits of the primitive representation.
     * Unsigned overflow of a * b will occur if and only if a * b >= 2^n.
     * Each side of the comparison must be re-written such that signed overflow will not occur:
     *
     *     [a.01]  a * b >= 2^n
     *     [a.02]  a * b > 2^n - 1
     *     [a.03]  a * b > ((2^(n-1) - 1) * 2) + 1
     *
     * Let M == Long.MAX_VALUE == 2^(n-1) - 1, and substitute:
     *
     *     [a.04]  a * b > (M * 2) + 1
     *
     * Assume the following identity for non-negative integer X and positive integer Y:
     *
     *     [b.01]  X == ((X / Y) * Y) + (X % Y)
     *
     * Let X == M and Y == b, and substitute:
     *
     *     [b.02]  M == ((M / b) * b) + (M % b)
     *
     * Substitute for M:
     *
     *     [a.04]  a * b > (M * 2) + 1
     *     [a.05]  a * b > ((((M / b) * b) + (M % b)) * 2) + 1
     *     [a.06]  a * b > ((M / b) * b * 2) + ((M % b) * 2) + 1
     *
     * Assume the following identity for non-negative integer X and positive integer Y:
     *
     *     [c.01]  X == ((X / Y) * Y) + (X % Y)
     *
     * Let X == ((M % b) * 2) + 1 and Y == b, and substitute:
     *
     *     [c.02]  ((M % b) * 2) + 1 == (((((M % b) * 2) + 1) / b) * b) + ((((M % b) * 2) + 1) % b)
     *
     * Substitute for ((M % b) * 2) + 1:
     *
     *     [a.06]  a * b > ((M / b) * b * 2) + ((M % b) * 2) + 1
     *     [a.07]  a * b > ((M / b) * b * 2) + (((((M % b) * 2) + 1) / b) * b) + ((((M % b) * 2) + 1) % b)
     *
     * Divide each side by b (// represents real division):
     *
     *     [a.08]  (a * b) // b > (((M / b) * b * 2) + (((((M % b) * 2) + 1) / b) * b) + ((((M % b) * 2) + 1) % b)) // b
     *     [a.09]  (a * b) // b > (((M / b) * b * 2) // b) + ((((((M % b) * 2) + 1) / b) * b) // b) + (((((M % b) * 2) + 1) % b) // b)
     *
     * Reduce each b-divided term that otherwise has a known factor of b:
     *
     *     [a.10]  a > ((M / b) * 2) + ((((M % b) * 2) + 1) / b) + (((((M % b) * 2) + 1) % b) // b)
     *
     * Let c == ((M % b) * 2) + 1), and substitute:
     *
     *     [a.11]  a > ((M / b) * 2) + (c / b) + ((c % b) // b)
     *
     * Assume the following tautology for integers X, Y and real Z such that 0 <= Z < 1:
     *
     *     [d.01]  X > Y + Z <==> X > Y
     *
     * Assume the following tautology for non-negative integer X and positive integer Y:
     *
     *     [e.01]  0 <= (X % Y) // Y < 1
     *
     * Let X == c and Y == b, and substitute:
     *
     *     [e.02]  0 <= (c % b) // b < 1
     *
     * Let X == a, Y == ((M / b) * 2) + (c / b), and Z == ((c % b) // b), and substitute:
     *
     *     [d.01]  X > Y + Z <==> X > Y
     *     [d.02]  a > ((M / b) * 2) + (c / b) + ((c % b) // b) <==> a > ((M / b) * 2) + (c / b)
     *
     * Drop the last term of the right-hand side:
     *
     *     [a.11]  a > ((M / b) * 2) + (c / b) + ((c % b) // b)
     *     [a.12]  a > ((M / b) * 2) + (c / b)
     *
     * Substitute for c:
     *
     *     [a.13]  a > ((M / b) * 2) + ((((M % b) * 2) + 1) / b)
     *
     * The first term of the right-hand side is clearly non-negative.
     * Determine the upper bound for the first term of the right-hand side (note that the least possible value of b == 2 produces the greatest possible value of (M / b) * 2):
     *
     *     [f.01]  (M / b) * 2 <= (M / 2) * 2
     *
     * Assume the following tautology for odd integer X:
     *
     *     [g.01]  (X / 2) * 2 == X - 1
     *
     * Let X == M and substitute:
     *
     *     [g.02]  (M / 2) * 2 == M - 1
     *
     * Substitute for (M / 2) * 2:
     *
     *     [f.01]  (M / b) * 2 <= (M / 2) * 2
     *     [f.02]  (M / b) * 2 <= M - 1
     *
     * The second term of the right-hand side is clearly non-negative.
     * Determine the upper bound for the second term of the right-hand side (note that the <= relation is preserved across positive integer division):
     *
     *     [h.01]  M % b < b
     *     [h.02]  M % b <= b - 1
     *     [h.03]  (M % b) * 2 <= (b - 1) * 2
     *     [h.04]  ((M % b) * 2) + 1 <= (b * 2) - 1
     *     [h.05]  (((M % b) * 2) + 1) / b <= ((b * 2) - 1) / b
     *     [h.06]  (((M % b) * 2) + 1) / b <= 1
     *
     * Since the upper bound of the first term is M - 1, and the upper bound of the second term is 1, the upper bound of the right-hand side is M.
     * Each side of the comparison has been re-written such that signed overflow will not occur.
     */
    final boolean unsignedMultiplyOverflows = (a > ((Long.MAX_VALUE / b) * 2L) + ((((Long.MAX_VALUE % b) * 2L) + 1L) / b));
    return unsignedMultiplyOverflows;
}

Answer 3

If one starts by determining which value is larger, there will be certain values of the larger and smaller number which guarantee that overflow can or cannot occur. Assume X is larger; Y is smaller.

If X is below 2^31, or if Y is less than 2, overflow is impossible; otherwise, if X is more than 2^62 or Y is not smaller than 2^32, overflow is certain. Return if either condition applies.

Otherwise, because of X's lower bound, V=(X>>31)<<31 is known to be between X and X/2. Because of X's upper bound, V>>31 is less than 2^31 Y is less than 2^32, T=(V>>31)*Y (also equal (X>>31)*Y) can be computed without overflow. Because V is a multiple of 2^31, T also equals (V*Y)>>31, so we know that T is between (X*Y)>>31 and (X*Y)>>32.

If T is less than 2^31, then X*Y must be less than 2^63 and overflow is impossible. If T is not less than 2^32, X*Y must be at least 2^63 and overflow is certain.

If neither condition applies, the product will be in the range 2^62 to 2^64. Overflow may be determined by doing the multiplication directly and checking the sign of the result. Unlike C, in which signed integer overflow yields Undefined Behavior, Java guarantees that if x and y are positive and x*y is less than 2^64, an arithmetic overflow will yield a negative result.

In summary, code should start by ranking X and Y, and then doing four comparisons and conditional returns. If none of them yields a dispositive result, it may compute (X>>31)*Y and doing two more comparisons. If those doesn't yield a dispositive result, one more multiply and test will yield a final answer using, in the worst case, eight comparisons, a shift, and two multiplies (if the rank of X and Y is not known, add another comparison to rank them).

Note that if the original numbers may be negative, some more checking is required to handle some extra cases. Still, the above approach should be faster than approaches requiring one or more divisions.