HN Explorer

9 comments

[ 2.1 ms ] story [ 34.3 ms ] thread
jollojou
The bug is an example of a problem associated with inductive inference. Relying on induction is tempting, and in most cases sufficient. However, this case proves that one should always be aware of the potential fallacy that is inherent in induction.
swolchok
or at least be aware that one is doing modulo arithmetic.
bigbang
Not just binary search. Anything that involves addition of signed integers could overflow.
patio11
Including, as I found to my embarassment recently, my license key generation logic.

Turns out that the maximum for a Java integer happens in the middle of the numerical representations of the values that I thought were valid license keys. "Whoops!"

(Happily, it turns out that all the keys actually assigned to customers were accepted by the broken version of the checker, too.)

mojuba 

  int mid = low + ((high - low) / 2);
is going to overflow if high and low have different signs. The correct version that works for any high and low is:

  int mid = sign(high) != sign(low) ?
    (high + low) / 2 : low + (high - low) / 2;
stuff4ben
True, but Java uses signed int's so the former should still work.
mojuba
That's the problem, if one int is negative and the other is positive, (high - low) may overflow.
amalcon
In this particular context, however, that should be just fine: low is clearly initialized to zero, and then only set to the value of this expression +1. As such, barring other bugs, low can never be negative.

Your point is valid, though, and worth bearing in mind in other circumstances.

jderick
I think a static checker such as Coverity would probably find this bug.