java - 如何检测Java中 "unsigned"长乘法的溢出？

Question

当然，Java 没有“无符号”长值，但有时有符号长值被有效地视为无符号长值(例如 System.nanoTime() 的结果)。从这个意义上说，算术溢出与其说是值的溢出，不如说是 64 位表示的溢出。示例:

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

测试乘法是否溢出似乎有些复杂，因为操作的符号会妨碍。注意到任何负值乘以 0 或 1 以外的任何值都会溢出无符号乘积可能会有所帮助，因为负值的最高位已设置。

确定两个“无符号”长值(实际上是有符号长值)的乘积是否会溢出 64 位表示的最佳方法是什么？使用 BigInteger 的实例是一个显而易见的解决方案，我推导出了一个仅涉及原始操作的复杂测试，但我觉得我遗漏了一些明显的东西。

Answer 1

给定两个我们假装成无符号长值的有符号长值，这里是如何确定无符号乘积是否会溢出，只使用有符号的原始操作(请原谅迂腐):

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;
}