为什么它输出 -294967296

huangapple go评论195阅读模式
英文:

Why does it output -294967296

问题

在Leetcode的4 Sum问题中,有一个测试案例[1000000000,1000000000,1000000000,1000000000],但由于某种原因,这些数字相加的结果等于-294967296,我不明白它是如何工作的。我认为这是因为实际答案大于int的最大值,但我尝试了这个方法,结果只是抛出了一个错误。所以为什么这里不会发生这种情况呢?

以下是您提供的代码,我不认为存在问题:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(target > Integer.MAX_VALUE || target < Integer.MIN_VALUE){
            return new ArrayList();
        }
        int lb = 0;
        int ub = nums.length - 1;
        int sum = 0;
        HashSet<List<Integer>> ans = new HashSet();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){

            for(int j = i + 1; j < nums.length; j++){
                lb = j + 1;
                ub = nums.length - 1;
                while(lb < ub){

                    sum = nums[i] + nums[j] + nums[lb] + nums[ub];
                    if(sum == -294967296){
                        System.out.println(sum);
                        System.out.println(nums[i]);
                        System.out.println(nums[j]);
                        System.out.println(nums[lb]);
                        System.out.println(nums[ub]);
                    }
                    if(sum == target){
                        ans.add(Arrays.asList(nums[i], nums[j], nums[lb], nums[ub]));
                        lb++;
                        ub--;
                    }else if(sum < target){
                        lb++;
                    }else{
                        ub--;
                    }

                }
            }
        }
        List<List<Integer>> ret = new ArrayList(ans);
        return ret;
    }
}

注意:您的代码中有一处可能会引发问题的地方。在处理整数溢出时,您检查了target是否超出了Integer的范围,但实际上应该在进行四数相加之前检查sum是否超出了Integer的范围。可以尝试将整数溢出的检查移到适当的位置。

英文:

So in leetcode 4 sum there is a test case [1000000000,1000000000,1000000000,1000000000] and for some reason the addition of these is equal to -294967296 and i do not understand how exactly this works i assumed it was because the actual answer is larger than max val of an int but i tried that and it just threw an error instead so why does that not happen here

class Solution {
public List&lt;List&lt;Integer&gt;&gt; fourSum(int[] nums, int target) {
if(target&gt;Integer.MAX_VALUE||target&lt;Integer.MIN_VALUE){
return new ArrayList();
}
int lb =0;
int ub  = nums.length-1;
int sum = 0;
HashSet&lt;List&lt;Integer&gt;&gt; ans = new HashSet();
Arrays.sort(nums);
for(int i = 0;i&lt;nums.length;i++){
for(int j = i+1;j&lt;nums.length;j++){
lb = j+1;
ub = nums.length-1;
while(lb&lt;ub){
sum = nums[i]+nums[j]+nums[lb]+nums[ub];
if(sum==-294967296){
System.out.println(sum);
System.out.println(nums[i]);
System.out.println(nums[j]);
System.out.println(nums[lb]);
System.out.println(nums[ub]);
}
if(sum==target){
ans.add(Arrays.asList(nums[i],nums[j],nums[lb],nums[ub]));
lb++;
ub--;
}else if(sum&lt;target){
lb++;
}else{
ub--;
}
}
}
}
List&lt;List&lt;Integer&gt;&gt; ret = new ArrayList(ans);
return ret;
}
}

this is the code i wrote and i dont think there is an issue here

答案1

得分: 0

首先...

if (target > Integer.MAX_VALUE || target < Integer.MIN_VALUE) {
    return new ArrayList();
}

这个 if 语句永远不会触发,因为根据定义,int 不能小于 Integer.MIN_VALUE 或大于 Integer.MAX_VALUE。换句话说,target > Integer.MAX_VALUE || target < Integer.MIN_VALUE 始终会评估为 false

一个 int 变量可以保存的最大值是 2^31 - 1,即 2,147,483,647。你的求和结果正好是 40 亿,这会导致整数变量溢出。

你真的应该使用 long 变量来处理这种数量级的值。

附注: 什么是 整数溢出?在 Java 中,byteshortintlong 数字都是使用二进制补码系统来存储的。值的第一个位用于存储符号。如果它等于 0,则数字为正;如果它等于 1,则数字为负。因此,int 可以保存的最大正值是二进制中的 01111111111111111111111111111111。这个数字恰好是 2,147,483,647 的十进制表示。如果你给它加 1,它会变成二进制中的 10000000000000000000000000000000,这对应的十进制表示是 -2,147,483,648(它为负数,因为第一个位现在变成了 1)。

英文:

First of all...

if(target&gt;Integer.MAX_VALUE||target&lt;Integer.MIN_VALUE){
return new ArrayList();
}

This if statement will never trigger because an int by definition cannot be smaller than Integer.MIN_VALUE or larger than Integer.MAX_VALUE. In other words, target &gt; Integer.MAX_VALUE || target &lt; Integer.MIN_VALUE will always evaluate to false.

The maximum value an int variable can hold is 2^31 - 1, or 2,147,483,647. Your sum is exactly 4 billion which causes your integer variable to overflow.

You really should use long variables to operate on values of this magnitude.

P.S. What does integer overflow mean? byte, short, int and long numbers in Java are stored using the 2's complement system. The first bit of the value stores the sign. If it's equal to 0, the number is positive; if it's 1, the number is negative. Thus the largest positive value an int can hold is 01111111111111111111111111111111 in binary. This number happens to be 2,147,483,647 in decimal. If you add 1 to it, it becomes 10000000000000000000000000000000, which is -2,147,483,648 in decimal (it's negative because the first bit is now 1).

答案2

得分: 0

这是一个计算溢出。简单来说,4 * 1000000000 超过了 Integer.MAX_VALUE。尽管处理器不会限制您的结果,但会将其包装到其可用位中。

您可以尝试使用十六进制表示:4 * 0x3B9ACA00 = 0xEE6B2800

System.out.println(0xEE6B2800);

只是另一个提示:您的代码已经非常复杂。您应该在需要它们的地方声明变量。lb 和 ub 的声明可以放在 for-j 循环中,sum 只在 while 循环中使用。这些初始值在设置为其他值之前从未被使用过。

在我的职业生涯中,我发现了许多这种在后续代码中被重新使用于其他目的的顶级变量,没有人真正能够预测它们有哪些值。

英文:

This is a calculation overflow. Simply put 4 * 1000000000 exceeds Integer.MAX_VALUE. Though the processor won't limit your result but wraps it into its available bits.

You can try using hexadecimal representation: 4 * 0x3B9ACA00 = 0xEE6B2800

System.out.println(0xEE6B2800);

Just another tip: Your code has a high complexity already. You should declare variables where you need them. The declarations of lb and ub could go into the for-j-loop, sum is only used within the while-loop. The initial values are never used before set to other values.

In my career I found lots of such top-level variables which ware reused in following code for other purposes and no one could really predict which values they have.

huangapple
  • 本文由 发表于 2023年8月11日 03:29:38
  • 转载请务必保留本文链接:https://go.coder-hub.com/76878795.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定