英文:
Adding 1 to Integer.MAX_VALUE in a loop causes unexpected behaviour (not the one where it goes to Integer.MIN_VALUE)
问题
我在解决 HackerRank 上的一个名为 "Array Manipulation" 的挑战时遇到了一个意外且有趣的问题。我正在运行一个大的 for 循环，在其中添加前缀和，但当我在前缀和中超过 Integer.MAX_VALUE（在这里，和以 int 存储的形式）时，数字会突然减少几千，而不是按照我预期的负值循环。
有人知道为什么会发生这种情况吗？如果将前缀和存储为 long，就没有问题。
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class ArrayManipulation {
public static long arrayManipulationPrefixSumLong(int n, int[][] queries) {
// ...（同上）
return maxInt;
}
public static int arrayManipulationPrefixSumInt(int n, int[][] queries) {
// ...（同上）
return maxInt;
}
public static void main(String[] args) {
Scanner scanner = null;
try {
// ...（同上）
//Relevant part
long arrayManipulationPrefixSumLong = arrayManipulationPrefixSumLong(n, queries);
int arrayManipulationPrefixSumInt = arrayManipulationPrefixSumInt(n, queries);
//Notice these two give different values
System.out.println("The long version: " + arrayManipulationPrefixSumLong);
System.out.println("The int version: " + arrayManipulationPrefixSumInt);
// Adding past the max value in a loop doesn't result in a negative number,
// to see this behaviour, increment the last line of input10ArrayManipulation_Subset85545 by 1.
System.out.println(Integer.MAX_VALUE - arrayManipulationPrefixSumLong);
//The below is my expected behaviour, where integer overflow occurs.
System.out.println("Max integer is: " + Integer.MAX_VALUE + " | Max integer +1 is: " + (Integer.MAX_VALUE + 1));
// ...（同上）
}
}
用于测试此程序的文本文件可以在以下位置找到：
https://drive.google.com/drive/folders/1ktlEixYsqeD2l4x12iD4gEVvM-1gVetK?usp=sharing
英文:
I was working on a HackerRank challenge for "Array Manipulation", and there was an unexpected, interesting problem encountered. I'm running a big for loop, where I'm adding prefix sums, and the moment I pass over Integer.MAX_Value in the prefix sum (where the sum is stored as an int), the number jumps down by a few thousand instead of looping into the negative which is my expected behaviour.
Anyone know why this could be occuring? There is no problem if you store the prefix sum as a long.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class ArrayManipulation {
public static long arrayManipulationPrefixSumLong(int n, int[][] queries) {
long[] array = new long[n];
for (int i = 0; i < queries.length; i++) {
int lowIndex = queries[i][0] - 1;
int highIndex = queries[i][1] - 1;
int addend = queries[i][2];
array[lowIndex] += addend;
if (highIndex + 1 < n)
array[highIndex + 1] -= addend;
}
long maxInt = 0;
for (int i = 0; i < array.length; i++) {
if (i != 0)
array[i] = array[i - 1] + array[i];
if (array[i] > maxInt)
maxInt = array[i];
}
return maxInt;
}
public static int arrayManipulationPrefixSumInt(int n, int[][] queries) {
int[] array = new int[n];
for (int i = 0; i < queries.length; i++) {
int lowIndex = queries[i][0] - 1;
int highIndex = queries[i][1] - 1;
int addend = queries[i][2];
array[lowIndex] += addend;
if (highIndex + 1 < n)
array[highIndex + 1] -= addend;
}
int maxInt = 0;
for (int i = 0; i < array.length; i++) {
if (i != 0)
array[i] = array[i - 1] + array[i];
if (array[i] > maxInt)
maxInt = array[i];
}
return maxInt;
}
public static void main(String[] args) {
Scanner scanner = null;
try {
scanner = new Scanner(new File("input10ArrayManipulation_Subset85545.txt"));
// scanner = new Scanner(new File("input10ArrayManipulation.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int n = scanner.nextInt();
// System.out.println(n);
int qn = scanner.nextInt();
// System.out.println(qn);
int[][] queries = new int[qn][3];
for (int i = 0; i < qn; i++) {
queries[i] = new int[]{scanner.nextInt(), scanner.nextInt(), scanner.nextInt()};
}
scanner.close();
System.out.println(new String(new char[85]).replace("\0", "*"));
System.out.println("Trying to find why exceeding Integer.MAX_VALUE in a loop causes unexpected behaviour.");
System.out.println(new String(new char[60]).replace("\0", "-"));
//Relevant part
long arrayManipulationPrefixSumLong = arrayManipulationPrefixSumLong(n, queries);
int arrayManipulationPrefixSumInt = arrayManipulationPrefixSumInt(n, queries);
//Notice these two give different values
System.out.println("The long version: " + arrayManipulationPrefixSumLong);
System.out.println("The int version: " + arrayManipulationPrefixSumInt);
// Adding past the max value in a loop doesn't result in a negative number,
// to see this behaviour, increment the last line of input10ArrayManipulation_Subset85545 by 1.
System.out.println(Integer.MAX_VALUE - arrayManipulationPrefixSumLong);
//The below is my expected behaviour, where integer overflow occurs.
System.out.println("Max integer is: " + Integer.MAX_VALUE + " | Max integer +1 is: " + (Integer.MAX_VALUE + 1));
System.out.println(new String(new char[60]).replace("\0", "-"));
System.out.println("Now testing with the other file that has 1 incremented on the last line, which makes it exceed the Integer.MAX_VALUE");
try {
scanner = new Scanner(new File("input10ArrayManipulation_Subset85545_increment1.txt"));
n = scanner.nextInt();
// System.out.println(n);
qn = scanner.nextInt();
// System.out.println(qn);
queries = new int[qn][3];
for (int i = 0; i < qn; i++) {
queries[i] = new int[]{scanner.nextInt(), scanner.nextInt(), scanner.nextInt()};
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
arrayManipulationPrefixSumLong = arrayManipulationPrefixSumLong(n, queries);
arrayManipulationPrefixSumInt = arrayManipulationPrefixSumInt(n, queries);
//Notice these two give different values
System.out.println("The long version: " + arrayManipulationPrefixSumLong);
System.out.println("The int version: " + arrayManipulationPrefixSumInt);
scanner.close();
}
}
The text files used to test this program can be found at:
https://drive.google.com/drive/folders/1ktlEixYsqeD2l4x12iD4gEVvM-1gVetK?usp=sharing
专注分享java语言的经验与见解，让所有开发者获益！
评论