java long 除法_解析java的addExact()与multiplyExact()

78 阅读 0 评论 52 点赞

我是靠谱客的博主执着茉莉，这篇文章主要介绍java long 除法_解析java的addExact()与multiplyExact()，现在分享给大家，希望可以做个参考。

java的加法在数字过大时是会溢出的，今天就遇到一个问题，要实现一个溢出时会抛出异常的加法函数。

这个问题细细一想却是复杂的很：不仅要考虑加法，输入参数还可以是负数反向溢出。好在java已经实现了该功能，直接阅读Math库的源码。

复制代码

1
2
3
4
5
6
7
8
public static long addExact(long x, long y) {
    long r = x + y;
    // HD 2-12 Overflow iff both arguments have the opposite sign of the result
    if (((x ^ r) & (y ^ r)) < 0) {
        throw new ArithmeticException("long overflow");
    }
    return r;
}

这个写法相当巧妙，首先我们知道java的int型在计算机中作为补码存储，而第一位是符号位（有时候会涉及到大小端存储，此处不影响叙述），直接决定了数字的正负。整个代码表面上是在对整个int做处理，实际有用的只有x y r的符号位而已。(0：正号 1：负号）下面列出x y r的符号位的真值表：

根据真值表反推，溢出只有“两个负数相加变成正数“和”两个正数相加变成负数“两种情况。考虑值域后确实如此。

在学习addExact()时，我意外收获了另一份有趣的代码，就是multiplyExact()。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int multiplyExact(int x, int y) {
    long r = (long)x * (long)y;
    if ((int)r != r) {
        throw new ArithmeticException("integer overflow");
    }
    return (int)r;
}
 
public static long multiplyExact(long x, long y) {
    long r = x * y;
    long ax = Math.abs(x);
    long ay = Math.abs(y);
    if (((ax | ay) >>> 31 != 0)) {
        // Some bits greater than 2^31 that might cause overflow
        // Check the result using the divide operator
        // and check for the special case of Long.MIN_VALUE * -1
        if (((y != 0) && (r / y != x)) ||
            (x == Long.MIN_VALUE && y == -1)) {
            throw new ArithmeticException("long overflow");
        }
    }
    return r;
}

int型的转成了long做暴力判断，而long就没办法了。

首先用((ax | ay) >>> 31 != 0)做了一个判断，等价于ax>2^31 || ay > 2^31。做这个判断一方面是为了排除不会溢出的情况，另一方面也暗示接下来的步骤比较费时。

果然接下来直接用除法做了逆运算。。这个思路倒是非常粗暴有效，但是其中的额外情况 x == Long.MIN_VALUE && y == -1 也算是一个非常微妙的漏洞。由于溢出，这个式子相乘的结果是Long.MAXVALUE+1，也就是Long.MINVALUE。但是，除法也溢出成了Long.MAXVALUE+1，还是Long.MINVALUE，导致变成了需要额外判断的特例。

标准库都是一群大牛精简出来的代码，因为一个特例导致多了这样一行代码，cpu周期多走了几个。想到他们殚精竭虑也没法把这个特例从代码中消除的样子，可以说是十分有趣了。