Java如何处理整数下溢和上溢?
接着上面的问题,你会如何检查/测试是否发生了这种情况?
Java如何处理整数下溢和上溢?
接着上面的问题,你会如何检查/测试是否发生了这种情况?
public static boolean willAdditionOverflow(int left, int right) {
if (right < 0 && right != Integer.MIN_VALUE) {
return willSubtractionOverflow(left, -right);
} else {
return (~(left ^ right) & (left ^ (left + right))) < 0;
}
}
public static boolean willSubtractionOverflow(int left, int right) {
if (right < 0) {
return willAdditionOverflow(left, -right);
} else {
return ((left ^ right) & (left ^ (left - right))) < 0;
}
}
long
替换来执行同样的int
检查。)
如果您认为这种情况可能会更加频繁,请考虑使用可以存储更大值的数据类型或对象,例如long
或者java.math.BigInteger
。最后一个不会溢出,实际上可用的JVM内存是限制。
如果你已经使用Java8,那么你可以使用新的Math#addExact()
和Math#subtractExact()
方法,在溢出时会抛出ArithmeticException
异常。
public static boolean willAdditionOverflow(int left, int right) {
try {
Math.addExact(left, right);
return false;
} catch (ArithmeticException e) {
return true;
}
}
public static boolean willSubtractionOverflow(int left, int right) {
try {
Math.subtractExact(left, right);
return false;
} catch (ArithmeticException e) {
return true;
}
}
当然,你也可以直接使用它们,而不是将它们隐藏在一个boolean
实用方法中。
98、99、100、-100、-99、-98……
。这样说是否更清楚了? - Austin AMath#addExact
语法 - 虽然通常会将其转换为Math.addExact
,但有时另一种形式仍然存在。 - Pokechu22对于原始整数类型而言,Java并不处理溢出/下溢(对于float和double类型,行为有所不同,它们将刷新为IEEE-754规定的+/-无穷大)。
当两个int相加时,如果发生溢出,你不会得到任何指示。检查溢出的简单方法是使用下一个更大的类型执行操作,并检查结果是否仍在源类型的范围内:
public int addWithOverflowCheck(int a, int b) {
// the cast of a is required, to make the + work with long precision,
// if we just added (a + b) the addition would use int precision and
// the result would be cast to long afterwards!
long result = ((long) a) + b;
if (result > Integer.MAX_VALUE) {
throw new RuntimeException("Overflow occured");
} else if (result < Integer.MIN_VALUE) {
throw new RuntimeException("Underflow occured");
}
// at this point we can safely cast back to int, we checked before
// that the value will be withing int's limits
return (int) result;
}
根据您的应用需求(抛出异常、刷到最大/最小值或只是记录下来),你可以在抛出异常子句的位置执行其他操作。如果您想要检测长运算中的溢出,基本类型就无法胜任了,可以使用 BigInteger。
编辑(2014-05-21):由于这个问题似乎经常被提及,并且我自己也不得不解决同样的问题,根据CPU计算其V标志的方式很容易评估溢出条件。
这基本上是一个涉及操作数符号和结果的布尔表达式:
/**
* Add two int's with overflow detection (r = s + d)
*/
public static int add(final int s, final int d) throws ArithmeticException {
int r = s + d;
if (((s & d & ~r) | (~s & ~d & r)) < 0)
throw new ArithmeticException("int overflow add(" + s + ", " + d + ")");
return r;
}
在Java中,更简单的方法是将表达式(在if中)应用于整个32位,并使用<0来检查结果(这将有效地测试符号位)。对于所有整数原始类型,原则完全相同,将上面方法中的所有声明更改为long使其适用于long。
对于较小的类型,由于隐式转换为int(有关位运算的详细信息,请参见JLS),因此需要显式掩码符号位进行检查(短操作数为0x8000,字节操作数为0x80,调整强制转换和参数声明):
/**
* Subtract two short's with overflow detection (r = d - s)
*/
public static short sub(final short d, final short s) throws ArithmeticException {
int r = d - s;
if ((((~s & d & ~r) | (s & ~d & r)) & 0x8000) != 0)
throw new ArithmeticException("short overflow sub(" + s + ", " + d + ")");
return (short) r;
}
(注意上面的示例使用了表达式,需要进行减法溢出检测)
那么这些布尔表达式是如何/为什么起作用的呢?首先,一些逻辑思考揭示了只有当两个参数的符号相同时才会发生溢出。因为,如果一个参数为负,一个参数为正,那么(加法)的结果必须更接近于零,或者在极端情况下,一个参数为零,与另一个参数相同。由于单独的参数本身不能创建溢出条件,它们的总和也不能创建溢出。
那么如果两个参数具有相同的符号会发生什么?让我们看看两个参数都是正数的情况:添加两个创建的总和大于类型MAX_VALUE的参数将始终产生负值,因此当arg1 + arg2 > MAX_VALUE时会发生溢出。现在可能出现的最大值是MAX_VALUE + MAX_VALUE(两个参数都是MAX_VALUE的极端情况)。对于一个字节(例如),这意味着127 + 127 = 254。查看从添加两个正值得到的所有值的位表示形式,可以发现那些溢出的值(128到254)都设置了第7位,而所有未溢出的值(0到127)都清除了第7位(最高位,符号)。这正是表达式的第一个(右侧)部分所检查的内容:
if (((s & d & ~r) | (~s & ~d & r)) < 0)
(~s & ~d & r)仅在两个操作数(s, d)均为正且结果(r)为负时才为真(该表达式适用于所有32位,但我们感兴趣的唯一位是最高位(符号位),被检查是否小于0)。
如果两个参数都是负数,它们的和永远不可能比任何一个参数更接近零,总和必须更接近负无穷大。我们可以产生的最极端的值是MIN_VALUE + MIN_VALUE,这(对于字节示例)显示了对于任何区间内的值(-1到-128),符号位都被设置,而任何可能溢出的值(-129到-256)都将清除符号位。因此,结果的符号再次揭示了溢出条件。这就是左半部分(s & d & ~r)检查的情况,其中两个参数(s, d)都是负数,并且结果为正数。逻辑在很大程度上等同于正数情况;如果发生下溢,所有可能由两个负值相加而得到的位模式都将清除符号位。
默认情况下,Java的int和long数学运算会在溢出和下溢时静默地进行循环。 (其他整数类型的整数操作是通过首先将操作数提升为int或long,根据JLS 4.2.2执行的。)
从Java 8开始,java.lang.Math
提供了对int和long参数执行命名操作的addExact
,subtractExact
,multiplyExact
,incrementExact
,decrementExact
和negateExact
静态方法,当溢出时抛出ArithmeticException异常。 (没有divideExact方法 - 您将需要自己检查一个特殊情况(MIN_VALUE / -1
)。)
toIntExact
方法将 long 强制转换为 int。如果 long 的值无法适配 int,则会抛出 ArithmeticException 异常。这对于通过未检查的 long 运算计算 int 和,在最后使用 toIntExact
转换为 int 可以很有用(但要小心不要让您的总和溢出)。MAX_VALUE
(这样检查起来不太方便)。Guava的基本类型实用类,如 SignedBytes
、UnsignedBytes
、Shorts
和 Ints
,提供 checkedCast
方法缩小大型类型(在下溢或上溢时引发 IllegalArgumentException,而不是 ArithmeticException),以及 saturatingCast
方法,在溢出时返回 MIN_VALUE
或 MAX_VALUE
。Java对于int和long原始类型的整数溢出都不进行任何处理,忽略正数和负数整数的溢出。
首先,本答案描述了整数溢出的定义,并举例说明即使在表达式计算中间值时也可能发生溢出,然后提供了链接到详细技术的资源,用于预防和检测整数溢出。
整数算术和表达式可能导致意外或未检测到的溢出,这是常见的编程错误。意外或未检测到的整数溢出也是一个众所周知的可利用的安全问题,尤其是因为它影响数组、堆栈和列表对象。
溢出可能出现在正向或负向,其中正向或负向的值将超出所讨论的原始类型的最大或最小值。在表达式或操作评估期间,中间值可能会发生溢出并影响表达式或操作的结果,最终值应该在范围内。
有时,负溢出被错误地称为下溢。当值比表示允许的值更接近零时,就会发生下溢。下溢在整数算术中发生,这是预期的。当整数评估在-1和0之间或0和1之间时会发生整数下溢。将产生一个分数结果截断为0。这是整数算术中正常而预期的,不被视为错误。然而,它可能导致代码抛出异常。例如,如果整数下溢的结果在表达式中用作除数,则会抛出“ArithmeticException: / by zero”的异常。
考虑以下代码:
int bigValue = Integer.MAX_VALUE;
int x = bigValue * 2 / 5;
int y = bigValue / x;
这会导致x被赋值为0,接着bigValue / x的运算会抛出异常"ArithmeticException: / by zero"(即除以零),而不是将y赋值为2。
对于x来说,预期结果应该是858,993,458,这个值小于最大int值2,147,483,647。然而,从计算Integer.MAX_VALUE * 2得到的中间结果是4,294,967,294,它超过了最大int值,并根据二进制补码整数表示法的规则变成-2。随后对-2 / 5的求值结果为0,这个值被赋给了x。
将计算x的表达式重新排列,使得在求积之前先进行除法运算。以下代码:
int bigValue = Integer.MAX_VALUE;
int x = bigValue / 5 * 2;
int y = bigValue / x;
x被赋值为858,993,458,y被赋值为2,这是我们预期的结果。
bigValue / 5的中间结果为429,496,729,它不超过int类型的最大值。对429,496,729 * 2的后续计算也不会超过int类型的最大值,因此x得到了预期的结果。y的计算没有除以零。x和y的计算结果都符合预期。
Java整数值的存储和行为遵循二进制补码有符号整数表示法。当一个结果值比最大或最小整数值还要大或小时,将得到一个二进制补码整数值。在非特别设计使用二进制补码行为的情况下,即大多数普通整数运算场景,可能导致程序逻辑或计算错误的就是这种二进制补码值,正如上面的例子所示。优秀的维基百科文章介绍了二进制补码: Two's complement - Wikipedia
有一些方法可以避免意外的整数溢出。这些技术可以分为三类:预条件测试、向上转型和BigInteger。
预条件测试包括检查进入算术操作或表达式的值,以确保这些值不会导致溢出。编程和设计需要创建测试以确保输入值不会导致溢出,然后确定如果发生将导致溢出的输入值该怎么办。
向上转型使用更大的原始类型来执行算术运算或表达式,然后确定结果值是否超过整数的最大或最小值。即使使用向上转型,也仍然有可能,某些操作或表达式中的值或某些中间值超过向上转型类型的最大或最小值,并引起溢出,这也无法被检测到,将导致意外和非预期的结果。通过分析或预条件可以防止在没有向上转型的情况下无法避免或实用时出现溢出。如果所涉及的整数已经是Java中的长整型,则无法使用原始类型进行向上转型。
BigInteger技术包括使用库方法使用BigInteger执行算术运算或表达式。BigInteger不会溢出。如果需要,它将使用所有可用内存。其算术方法通常只比整数操作略慢一点。但结果使用BigInteger可能仍然超过所需基本类型结果的最大或最小值,因此在编程和设计中仍需要确定如果BigInteger结果超过所需基本类型结果(例如int或long),该怎么办。
卡内基梅隆软件工程研究所的CERT计划和Oracle已经创建了一组安全Java编程标准。该标准包括预防和检测整数溢出的技术。这个标准在这里作为一个免费的在线资源发布:The CERT Oracle Secure Coding Standard for Java
该标准的章节描述和包含了有关预防或检测整数溢出的编码技巧的实际例子,可以在这里找到:NUM00-J. Detect or prevent integer overflow
The CERT Oracle Secure Coding Standard for Java的书籍形式和PDF形式也可用。</
我自己也遇到了这个问题,以下是我的解决方案(适用于乘法和加法):
static boolean wouldOverflowOccurwhenMultiplying(int a, int b) {
// If either a or b are Integer.MIN_VALUE, then multiplying by anything other than 0 or 1 will result in overflow
if (a == 0 || b == 0) {
return false;
} else if (a > 0 && b > 0) { // both positive, non zero
return a > Integer.MAX_VALUE / b;
} else if (b < 0 && a < 0) { // both negative, non zero
return a < Integer.MAX_VALUE / b;
} else { // exactly one of a,b is negative and one is positive, neither are zero
if (b > 0) { // this last if statements protects against Integer.MIN_VALUE / -1, which in itself causes overflow.
return a < Integer.MIN_VALUE / b;
} else { // a > 0
return b < Integer.MIN_VALUE / a;
}
}
}
boolean wouldOverflowOccurWhenAdding(int a, int b) {
if (a > 0 && b > 0) {
return a > Integer.MAX_VALUE - b;
} else if (a < 0 && b < 0) {
return a < Integer.MIN_VALUE - b;
}
return false;
}
如果有错误或可以简化的地方,请随意更正。我已经对乘法方法进行了一些测试,主要是边缘情况,但仍然可能存在问题。
int*int
,我认为简单地将其转换为 long
并查看结果是否适合 int
将是最快的方法。对于 long*long
,如果将操作数规范化为正数,则可以将每个操作数分成上下两个 32 位半部分,将每个半部分提升为 long(要小心符号扩展!),然后计算两个部分乘积 [其中一个上半部分应为零]。 - supercatpublic class Test {
public static void main(String[] args) {
int i = Integer.MAX_VALUE;
int j = Integer.MIN_VALUE;
System.out.println(i+1);
System.out.println(j-1);
}
}
打印
-2147483648
2147483647
addExact()
和multiplyExact()
这样的方法,当发生溢出时,它们会抛出ArithmeticException
异常。if((A >= 0 && B >= 0) && (resultOfAdd < A || resultOfAdd < B))
,由于它回绕到预期范围内。不过,可能有更聪明的方法来检查单个计算。对于两个 int
,您可以检查它们的 long
值之和是否等于它们的 int
值之和。您可以使用任意精度类型来检查更大的值。 - user904963有一些库提供了安全的算术操作,可以检查整数溢出/下溢。例如,Guava的IntMath.checkedAdd(int a, int b)返回a
和b
的和,只要它不会溢出,并在有符号int
算术中a + b
溢出时抛出ArithmeticException
异常。
Math
类包含类似的代码。 - Maarten Bodewespublic int multiplyBy2(int x) throws ArithmeticException {
long result = 2 * (long) x;
if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE){
throw new ArithmeticException("Integer overflow");
}
return (int) result;
}
它并没有做任何事情——上溢/下溢只是发生了。
由于溢出而产生的“-1”与其他信息导致的“-1”没有区别。因此,您无法通过某些状态或仅检查值来确定是否发生了溢出。
但是,如果有必要的话,您可以聪明地进行计算以避免溢出,或者至少知道何时会发生。你的情况是什么?
static final int safeAdd(int left, int right)
throws ArithmeticException {
if (right > 0 ? left > Integer.MAX_VALUE - right
: left < Integer.MIN_VALUE - right) {
throw new ArithmeticException("Integer overflow");
}
return left + right;
}
static final int safeSubtract(int left, int right)
throws ArithmeticException {
if (right > 0 ? left < Integer.MIN_VALUE + right
: left > Integer.MAX_VALUE + right) {
throw new ArithmeticException("Integer overflow");
}
return left - right;
}
static final int safeMultiply(int left, int right)
throws ArithmeticException {
if (right > 0 ? left > Integer.MAX_VALUE/right
|| left < Integer.MIN_VALUE/right
: (right < -1 ? left > Integer.MIN_VALUE/right
|| left < Integer.MAX_VALUE/right
: right == -1
&& left == Integer.MIN_VALUE) ) {
throw new ArithmeticException("Integer overflow");
}
return left * right;
}
static final int safeDivide(int left, int right)
throws ArithmeticException {
if ((left == Integer.MIN_VALUE) && (right == -1)) {
throw new ArithmeticException("Integer overflow");
}
return left / right;
}
static final int safeNegate(int a) throws ArithmeticException {
if (a == Integer.MIN_VALUE) {
throw new ArithmeticException("Integer overflow");
}
return -a;
}
static final int safeAbs(int a) throws ArithmeticException {
if (a == Integer.MIN_VALUE) {
throw new ArithmeticException("Integer overflow");
}
return Math.abs(a);
}
checked
。我很少看到它被使用,而键入checked { code; }
的工作量与调用方法差不多。 - Maarten Bodewescsc /checked ...
或在 Visual Studio 中的项目属性窗格中设置该属性。 - Drew Noakes