java if (a - b < 0) 和 if (a < b) 的区别

Difference between if (a - b < 0) and if (a < b)

提问by dejvuth

I was reading Java's ArrayListsource code and noticed some comparisons in if-statements.

我正在阅读 Java 的ArrayList源代码并注意到 if 语句中的一些比较。

In Java 7, the method grow(int)uses

在 Java 7 中，该方法grow(int)使用

if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

In Java 6, growdidn't exist. The method ensureCapacity(int)however uses

在 Java 6 中，grow不存在。ensureCapacity(int)然而该方法使用

if (newCapacity < minCapacity)
    newCapacity = minCapacity;

What was the reason behind the change? Was it a performance issue or just a style?

改变背后的原因是什么？这是性能问题还是只是一种风格？

I could imagine that comparing against zero is faster, but performing a complete subtraction just to check whether it's negative seems a bit overkill to me. Also in terms of bytecode, this would involve two instructions (ISUBand IF_ICMPGE) instead of one (IFGE).

我可以想象与零进行比较会更快，但是执行完全减法只是为了检查它是否为负数对我来说似乎有点矫枉过正。同样在字节码方面，这将涉及两条指令（ISUB和IF_ICMPGE）而不是一条（IFGE）。

回答by Tunaki

a < band a - b < 0can mean two different things. Consider the following code:

a < b并且a - b < 0可能意味着两件不同的事情。考虑以下代码：

int a = Integer.MAX_VALUE;
int b = Integer.MIN_VALUE;
if (a < b) {
    System.out.println("a < b");
}
if (a - b < 0) {
    System.out.println("a - b < 0");
}

When run, this will only print a - b < 0. What happens is that a < bis clearly false, but a - boverflows and becomes -1, which is negative.

运行时，这只会打印a - b < 0. 发生的事情a < b显然是错误的，但a - b溢出并变成-1，这是负数。

Now, having said that, consider that the array has a length that is really close to Integer.MAX_VALUE. The code in ArrayListgoes like this:

现在，话虽如此，请考虑数组的长度非常接近Integer.MAX_VALUE。里面的代码ArrayList是这样的：

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);

oldCapacityis really close to Integer.MAX_VALUEso newCapacity(which is oldCapacity + 0.5 * oldCapacity) might overflow and become Integer.MIN_VALUE(i.e. negative). Then, subtracting minCapacityunderflowsback into a positive number.

oldCapacity真的很接近Integer.MAX_VALUE所以newCapacity（即oldCapacity + 0.5 * oldCapacity）可能会溢出并变为Integer.MIN_VALUE（即负数）。然后，将minCapacity下溢减去回正数。

This check ensures that the ifis not executed. If the code were written as if (newCapacity < minCapacity), it would be truein this case (since newCapacityis negative) so the newCapacitywould be forced to minCapacityregardless of the oldCapacity.

此检查可确保if不执行。如果代码被写成if (newCapacity < minCapacity)，这将是true在这种情况下（因为newCapacity是负的），因此newCapacity将被迫minCapacity不管oldCapacity。

This overflow case is handled by the next if. When newCapacityhas overflowed, this will be true: MAX_ARRAY_SIZEis defined as Integer.MAX_VALUE - 8and Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0is true. The newCapacityis therefore rightly handled: hugeCapacitymethod returns MAX_ARRAY_SIZEor Integer.MAX_VALUE.

这种溢出情况由下一个 if 处理。当newCapacity溢出时，这将是true:MAX_ARRAY_SIZE定义为Integer.MAX_VALUE - 8并且Integer.MIN_VALUE - (Integer.MAX_VALUE - 8) > 0是true。将newCapacity因此被正确地处理：hugeCapacity方法返回MAX_ARRAY_SIZE或Integer.MAX_VALUE。

NB: this is what the // overflow-conscious codecomment in this method is saying.

注意：这就是// overflow-conscious code这个方法中的评论所说的。

回答by Eran

I found this explanation:

我找到了这个解释：

On Tue, Mar 9, 2010 at 03:02, Kevin L. Stern wrote:

I did a quick search and it appears that Java is indeed two's complement based. Nonetheless, please allow me to point out that, in general, this type of code worries me since I fully expect that at some point someone will come along and do exactly what Dmytro suggested; that is, someone will change:

if (a - b > 0)

to

if (a > b)

and the entire ship will sink. I, personally, like to avoid obscurities such as making integer overflow an essential basis for my algorithm unless there is a good reason to do so. I would, in general, prefer to avoid overflow altogether and to make the overflow scenario more explicit:

if (oldCapacity > RESIZE_OVERFLOW_THRESHOLD) {
   // Do something
} else {
  // Do something else
}

It's a good point.

In ArrayListwe cannot do this (or at least not compatibly), because ensureCapacityis a public API and effectively already accepts negative numbers as requests for a positive capacity that cannot be satisfied.

The current API is used like this:

int newcount = count + len;
ensureCapacity(newcount);

If you want to avoid overflow, you would need to change to something less natural like

ensureCapacity(count, len);
int newcount = count + len;

Anyway, I'm keeping the overflow-conscious code, but adding more warning comments, and "out-lining" huge array creation so that ArrayList's code now looks like:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;

    // Overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // Overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

Webrev regenerated.

Martin

2010 年 3 月 9 日，星期二 03:02，Kevin L. Stern 写道：

我进行了快速搜索，看来 Java 确实是基于二进制补码的。尽管如此，请允许我指出，总的来说，这种类型的代码让我感到担忧，因为我完全希望在某个时候有人会出现并完全按照 Dmytro 的建议行事；也就是说，有人会改变：

if (a - b > 0)

到

if (a > b)

整艘船都会沉没。我个人喜欢避免晦涩难懂的事情，例如将整数溢出作为我算法的基本基础，除非有充分的理由这样做。一般来说，我更愿意完全避免溢出并使溢出场景更加明确：

if (oldCapacity > RESIZE_OVERFLOW_THRESHOLD) {
   // Do something
} else {
  // Do something else
}

这是一个很好的观点。

在ArrayList我们不能做到这一点（或至少不兼容），因为 ensureCapacity是一个公共的API，有效地接受已经为负数的不能满足一个积极的容量请求。

当前的 API 是这样使用的：

int newcount = count + len;
ensureCapacity(newcount);

如果你想避免溢出，你需要改变一些不太自然的东西，比如

ensureCapacity(count, len);
int newcount = count + len;

无论如何，我保留了溢出意识代码，但添加了更多警告注释，并“概述”了巨大的数组创建，因此 ArrayList现在的代码如下所示：

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;

    // Overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // Overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

韦雷夫重生。

马丁

In Java 6, if you use the API as:

在 Java 6 中，如果您将 API 用作：

int newcount = count + len;
ensureCapacity(newcount);

And newCountoverflows (this becomes negative), if (minCapacity > oldCapacity)will return false and you may mistakenly assume that the ArrayListwas increased by len.

并且newCount溢出（这变为负数），if (minCapacity > oldCapacity)将返回 false，您可能会错误地认为ArrayList增加了len。

回答by Erick G. Hagstrom

Looking at the code:

查看代码：

int newCapacity = oldCapacity + (oldCapacity >> 1);

If oldCapacityis quite large, this will overflow, and newCapacitywill be a negative number. A comparison like newCapacity < oldCapacitywill incorrectly evaluate trueand the ArrayListwill fail to grow.

如果oldCapacity很大，这将溢出，并且newCapacity将是一个负数。比较像newCapacity < oldCapacity会错误地评估true并且ArrayList不会增长。

Instead, the code as written (newCapacity - minCapacity < 0returns false) will allow the negative value of newCapacityto be further evaluated in the next line, resulting in recalculating newCapacityby invoking hugeCapacity(newCapacity = hugeCapacity(minCapacity);) to allow for the ArrayListto grow up to MAX_ARRAY_SIZE.

相反，所编写的代码（newCapacity - minCapacity < 0返回 false）将允许newCapacity在下一行中进一步评估的负值，导致newCapacity通过调用hugeCapacity( newCapacity = hugeCapacity(minCapacity);)重新计算以允许ArrayList增长到MAX_ARRAY_SIZE。

This is what the // overflow-conscious codecomment is trying to communicate, though rather obliquely.

这就是// overflow-conscious code评论试图传达的内容，尽管相当间接。

So, bottom line, the new comparison protects against allocating an ArrayListlarger than the predefined MAX_ARRAY_SIZEwhile allowing it to grow right up to that limit if needed.

因此，最重要的是，新的比较可以防止分配ArrayList大于预定义的值，MAX_ARRAY_SIZE同时允许它在需要时增长到该限制。

回答by Doradus

The two forms behave exactly the same unless the expression a - boverflows, in which case they are opposite. If ais a large negative, and bis a large positive, then (a < b)is clearly true, but a - bwill overflow to become positive, so (a - b < 0)is false.

这两种形式的行为完全相同，除非表达式a - b溢出，在这种情况下它们是相反的。如果a是大的负数，又b是大的正数，那么(a < b)显然是真的，但是a - b会溢出变成正数，所以(a - b < 0)是假的。

If you're familiar with x86 assembly code, consider that (a < b)is implemented by a jge, which branches around the body of the if statement when SF = OF. On the other hand, (a - b < 0)will act like a jns, which branches when SF = 0. Hence, these behave differently precisely when OF = 1.

如果您熟悉 x86 汇编代码，请考虑它(a < b)是由 a 实现的jge，当 SF = OF 时，它围绕 if 语句的主体分支。另一方面，(a - b < 0)将像 a 一样jns，在 SF = 0 时分支。因此，当 OF = 1 时，它们的行为完全不同。