在long中使用long会导致java中溢出的额外情况。为什么？

我为Hackerrank挑战写了一个解决方案，其中我将大量的数字总和为一个总变量。当我使用整数时，我注意到我在一个测试用例中溢出，但所有其他测试用例都输出了正确的答案。当我将我的total变量切换到很长时间以避免溢出时，我开始在两个测试用例（与之前相同并且另一个）溢出。一旦我将total，numToSell,和lastMax改为长整数，程序就会计算出正确的答案。在long中使用long会导致java中溢出的额外情况。为什么？

什么会导致这种情况发生？我期望从int到long的变量不应该导致溢出。

import java.util.*; 

public class Solution { 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int T = in.nextInt(); 
     while(T-->0) 
     { 
      int N = in.nextInt(); 
      int[] price = new int[N]; 

      for(int i = 0; i < N; ++i) 
      { 
       price[i] = in.nextInt(); 
      } 

      int lastMax = price[N-1]; //works when this and numToSell are longs 
      int numToSell = 0; 
      long total = 0; //if this is also an int, only overflows in one case in my samples 
      for(int i = N - 2; i >= 0; --i) 
      { 
       if(price[i] <= lastMax) 
       { 
        ++numToSell; 
        total -= price[i]; 
       } 
       else 
       { 
        total += numToSell*lastMax; 
        lastMax = price[i]; 
        numToSell = 0; 
       } 
      } 
      total += numToSell*lastMax; 
      System.out.println(total); 

     } 
    } 
}

在受影响的试验情况下，N是39384和阵列中的每个数字是是整数1和100000

来源

2014-09-19 dgollahon

你能提供导致问题的最小量的输入数据吗？ – Bohemian 2014-09-19 02:36:39

我想你可以使用调试器来回答你自己的问题，也许可以对变量的符号进行一些抽查。 – 2014-09-19 02:44:53

如果总，numToSell和lastMax，都是整数，有些情况下可能会取消并意外地给你正确的答案。这不一定发生，如果总数很长，但另一个是整数。

下面是一个遍历循环的例子。

prices = {2000001,2000000,2000000,2000000}; 
lastMax = 2000000; 
numToSell = 0; 
total = 0; 
loop: 
    iteration 1: 
    numToSell = 1; 
    total = -2000000 
    iteration 2: 
    numToSell = 2; 
    total = -4000000 // oh no, we underflowed if we are int, but not long! 
    iteration 3: 
    total = -4000000 + (2 * 2000000) // let's take a deeper look at this below 
    numToSell = 0; 
    lastMax = 20000001 
total += 0;

让我们来看看这条线：总= -4000000 +（2×200万）

如果总，numToSell和lastMax都是整数，则总= 0。这是因为总溢和（2 * 20000000）将以完全相同的方式溢出。所以这两个取消了。

如果他们都是多头，再没有什么溢出所以总= -40000000 +（2×200万）= 0。

如果总长，则总没当它被设置为-4000000溢。但是，（2 * 2000000）是一个整数，它会溢出并成为负数。所以总数不会为零！

这是一个案件，当所有的整数工作，所有多头工作，但混合失败。

来源

2014-09-19 02:53:03 Ian

啊，你说得对。我知道int * int会做32位乘法，但我认为numToSell * lastMax太小而不能溢出int，但实际上它们可能是50k * 100k = 50亿。在我的具体案例中，最后的总计操作是-1897992076 + -426605980 = 1970369240，这在某种程度上是神奇的。法官似乎在除了这个特定的多个隐藏的测试案例上发生了这种情况。 – dgollahon 2014-09-19 03:42:46

是如果numToSell和lastMaxint之间，因为在这里

total += numToSell*lastMax;

是乘法。 int * int = int。然后，您将int添加到您的long。当numToSell（或lastMax）是一个特定的乘法指令将按预期工作很长时间。我注意到你在两个地方执行这个数学。

来源

2014-09-19 02:40:06

，如果你只是改变total长和左numToSell和lastMax为INT我猜，然后numToSell*lastMax仍然会溢出，给你不正确的结果，然后将其添加到total

来源

2014-09-19 02:42:04 anonymous

在long中使用long会导致java中溢出的额外情况。为什么？

回答

相关问题