数值溢出问题

前言

数值溢出,不得不考虑的问题…

什么是溢出

以Java语言为例,整数类型的上下溢出如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// author: SilenceZheng66
public class Overflow {
public static void main(String[] args) {
int posMax = 0b1111111111111111111111111111111;
int negMin = -0b1111111111111111111111111111111;

System.out.println(posMax); // 2147483647
System.out.println(posMax+1); // -2147483648
System.out.println(posMax+2); // -2147483647

System.out.println(negMin); // -2147483647
System.out.println(negMin-1); // -2147483648
System.out.println(negMin-2); // 2147483647
}
}

一旦出现溢出,程序的运行结果就变得不可控,逻辑上成立的算法实际上无法得到想要的结果,需要考虑数据类型的上下界限。

如何防止数值溢出

以二分查找为例,查找在1到n内的某整数,若输入n为int型,则可能产生上溢出:mid = (start + end)/2;。

此处start的最小值为1,end的最大值为2147483647,在start+end值大于2147483647时就会发生上溢出。

一种聪明的解决办法是将求中位数的操作改变为:mid = start + (end - start)/2;,此时由于end不会超过int的上界,故不会发生溢出。

另一种解决办法是将求和操作放到long型中计算,然后转回int型,相较于上一种内存消耗增加:

1
2
3
// author: SilenceZheng66
long midL = ((long)start + (long)end)/2;
mid = (int) midL;

后记

首发于 silencezheng.top,转载请注明出处。


数值溢出问题
http://silencezheng.top/2022/12/16/article84/
作者
SilenceZheng66
发布于
2022年12月16日
许可协议