如何在Java中检查两个数字相乘是否会导致溢出？

Question

我想处理两个数字相乘导致溢出的特殊情况。代码大致如下：

int a = 20;
long b = 30;

// if a or b are big enough, this result will silently overflow
long c = a * b;

那是一个简化版本。在真实的程序中，a 和 b 在运行时会从其他地方获取。我想要实现的是像这样的东西：

long c;
if (a * b will overflow) {
    c = Long.MAX_VALUE;
} else {
    c = a * b;
}

你认为我应该如何最好地编写代码？

更新：在我的情况下，a和b始终是非负的。

- Steve McLeod

---

很遗憾，Java无法像C#一样提供对CPU的溢出标志进行间接访问。请参考C#的实现方法。 - Drew Noakes

Answer 1

Java 8提供了用于整数和长整数的Math.multiplyExact，Math.addExact等函数。当发生溢出时，这些函数会抛出未经检查的ArithmeticException异常。

- bcoughlan

Answer 2

如果a和b都是正数，则可以使用以下内容：

if (a != 0 && b > Long.MAX_VALUE / a) {
    // Overflow
}

如果您需要处理正数和负数，则情况会更加复杂：

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if (a != 0 && (b > 0 && b > maximum / a ||
               b < 0 && b < maximum / a))
{
    // Overflow
}

我制作了一个小表格来检查这个问题，假装溢出会发生在-10或+10：

a =  5   b =  2     2 >  10 /  5
a =  2   b =  5     5 >  10 /  2
a = -5   b =  2     2 > -10 / -5
a = -2   b =  5     5 > -10 / -2
a =  5   b = -2    -2 < -10 /  5
a =  2   b = -5    -5 < -10 /  2
a = -5   b = -2    -2 <  10 / -5
a = -2   b = -5    -5 <  10 / -2

- John Kugelman

---

我应该提到，在我的情况下，a和b始终是非负的，这会在某种程度上简化这种方法。 - Steve McLeod

我认为这可能会导致一个问题：a = -1，b = 10。当没有溢出时，最大/ a表达式的结果为Integer.MIN_VALUE并检测到溢出。 - Kyle

这真的很好。对于那些想知道的人，这个方法有效的原因是对于整数n，n>x和n>floor（x）是相同的。对于正整数，除法会进行一个隐式的向下取整（对于负数则向上取整）。 - Thomas Ahle

为了解决 a = -1 和 b = 10 的问题，请参见我的下面的答案。 - Jim Pivarski

Answer 3

有一些Java库提供安全算术操作，这些操作可以检查长整型的溢出/下溢。例如，Guava的LongMath.checkedMultiply(long a, long b)返回a和b的乘积，如果不会溢出的话，并在有符号long算术中溢出时抛出ArithmeticException异常。

- reprogrammer

---

这是最佳答案--使用一个由真正理解Java机器算术的人实现并经过许多人测试的库。不要尝试编写自己的代码或使用其他答案中发布的未经充分测试的半成品代码！ - Rich

@Enerccio -- 我不理解你的评论。你是在说Guava不能在所有系统上运行吗？我可以向你保证，它将在Java支持的所有地方都能正常工作。如果你是在说重用代码是一个不好的想法，我不同意。 - Rich

@Rich，我是说包含大量库以便使用一个函数是个不好的主意。 - Enerccio

为什么？如果你正在编写一个大型应用程序，例如企业级应用，那么在类路径上添加一个额外的JAR不会造成任何伤害，而Guava中有许多非常有用的代码。重用他们经过精心测试的代码比尝试编写自己的版本要好得多（我想这就是你推荐的吧？）。如果你正在编写一个额外的JAR非常昂贵的环境中（在哪里？嵌入式Java？），那么也许你应该从Guava中提取出这个类。抄袭StackOverflow上未经测试的答案比复制Guava经过精心测试的代码更好吗？ - Rich

一个条件判断语句就能处理的问题，用抛出异常的方式是否有些过头了？ - victtim

如果您想避免异常，也许使用"SaturatedMultiply"更好。 - victtim

Answer 4

这是我能想到的最简单的方法。

int a = 20;
long b = 30;
long c = a * b;

if(c / b == a) {
   // Everything fine.....no overflow
} else {
   // Overflow case, because in case of overflow "c/b" can't equal "a"
}

- Naren

Answer 5

你可以使用java.math.BigInteger代替，并检查结果的大小（未测试代码）：

BigInteger bigC = BigInteger.valueOf(a) * multiply(BigInteger.valueOf(b));
if(bigC.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
  c = Long.MAX_VALUE;
} else {
  c = bigC.longValue()
}

- Ulf Lindback

---

我觉得这个解决方案相当缓慢。 - nothrow

这可能是最好的方法。虽然我一开始没有推荐它，因为我认为这是一个数值应用程序，但这确实可能是解决这个问题的最佳方法。 - Stefan Kendall

我不确定您是否可以在 BigInteger 中使用 '>' 运算符，应该使用 compareTo 方法。 - Pierre

已更改为compareTo，速度可能很重要，也可能不重要，这取决于代码将被使用的情况。 - Ulf Lindback

Answer 6

我希望在不直接编辑替换John Kugelman的答案的基础上加以完善。它适用于他的测试用例(MIN_VALUE = -10, MAX_VALUE = 10)，因为MIN_VALUE == -MAX_VALUE的对称性，但对于二进制补码整数并非如此。实际上，MIN_VALUE == -MAX_VALUE - 1。

scala> (java.lang.Integer.MIN_VALUE, java.lang.Integer.MAX_VALUE)
res0: (Int, Int) = (-2147483648,2147483647)

scala> (java.lang.Long.MIN_VALUE, java.lang.Long.MAX_VALUE)
res1: (Long, Long) = (-9223372036854775808,9223372036854775807)

当应用于真正的MIN_VALUE和MAX_VALUE时，John Kugelman的答案在a == -1和b ==任何其他值（Kyle首先提出了这个问题）时会产生溢出情况。以下是解决方法：

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if ((a == -1 && b == Long.MIN_VALUE) ||
    (a != -1 && a != 0 && ((b > 0 && b > maximum / a) ||
                           (b < 0 && b < maximum / a))))
{
    // Overflow
}

这不是针对任何MIN_VALUE和MAX_VALUE的通用解决方案，但它对于Java的Long和Integer以及任何值的a和b都是通用的。

- Jim Pivarski

---

我认为这样做会使它变得过于复杂，因为此解决方案仅在 MIN_VALUE = -MAX_VALUE - 1 的情况下有效，而不适用于任何其他情况（包括你的示例测试用例）。我需要进行大量更改。 - Jim Pivarski

由于原帖的需求已经超出了范围，像我这样的人找到这个页面是因为他们需要一个更一般的解决方案（处理负数而不仅仅是Java 8）。实际上，由于此解决方案不涉及任何超出纯算术和逻辑之外的函数，因此它也可以用于C或其他语言。 - Jim Pivarski

Answer 7

使用对数来检查结果的大小。

- High Performance Mark

---

你的意思是：ceil(log(a)) + ceil(log(b)) > log(Long.MAX)吗？ - Thomas Jung

我已经检查过了。对于小值，它比BigInteger快20％，对于接近MAX的值，它几乎相同（快5％）。 Yossarian的代码是最快的（比BigInteger快95％和75％）。 - Thomas Jung

我相当怀疑它在某些情况下可能会失败。 - Tom Hawtin - tackline

抱歉，我认为在AND掩码（0xffffffff80000000L）中需要设置一个额外的位——现在有点晚了，但你明白我的意思... - Neil Coffey

Long.numberOfTrailingZeros(a) + Long.numberOfTrailingZeros(b) 应该很快，但并不总是足以确定。 - 4esn0k

Answer 8

Java有类似于int.MaxValue的东西吗？如果有，请尝试使用以下代码：

if (b != 0 && Math.abs(a) > Math.abs(Long.MAX_VALUE / b))
{
 // it will overflow
}

编辑：在问题中看到了Long.MAX_VALUE

- nothrow

---

我没有给它点踩，但是如果a是Long.MIN_VALUE，Math.Abs(a)就不起作用。 - John Kugelman

@John - a和b都大于0。我认为Yossarian的方法（b！= 0 && a> Long.MAX_VALUE / b）是最好的。 - Thomas Jung

@Thomas，a和b都是>=0的，也就是非负数。 - Steve McLeod

没错，但在这种情况下，不需要使用绝对值函数。如果允许负数，则至少有一个边缘情况会失败。我只是在挑剔而已。 - John Kugelman

在Java中，您必须使用Math.abs而不是Math.Abs（C#人士？） - dfa

如果a==1，且b==Long.MIN_VALUE，则此方法会溢出，但实际上它并没有。 - Brian

Answer 9

从jruby中盗取

    long result = a * b;
    if (a != 0 && result / a != b) {
       // overflow
    }

更新：这段代码很短且效果良好；但是，当a = -1，b = Long.MIN_VALUE时会失败。

一种可能的改进方法：

long result = a * b;
if( (Math.signum(a) * Math.signum(b) != Math.signum(result)) || 
    (a != 0L && result / a != b)) {
    // overflow
}

请注意，这将捕获一些溢出而无需进行任何除法。

- rogerdpack

---

你可以使用 Long.signum 代替 Math.signum。 - aditsu quit because SE is EVIL

Answer 10

正如所指出的那样，Java 8有Math.xxxExact方法，可以在溢出时抛出异常。

如果您的项目没有使用Java 8，您仍然可以“借用”它们的实现，它们非常紧凑。

以下是这些实现在JDK源代码库中的链接。无法保证这些链接是否仍然有效，但无论如何，您都应该能够下载JDK源代码并查看它们在java.lang.Math类中的魔法。

Math.multiplyExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l925

Math.addExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l830

更新：将无效链接更换为指向Open JDK的Mercurial存储库的链接。

- StFS