P
Peter Duniho
It's a way of subdividing the "narrow it down" portion of the algorithm, to
maximize speed while still allowing for accuracy.
In particular, note that after the first loop, you now have an upper bound
on the maximum possible value for the variable. That is, y + y. You know
that y <= max < y + y.
So, the second loop tries to traverse the distance between y and y + y as
quickly as possible. It does this by first trying to go half the distance.
If that doesn't work, it cuts the distance in half and tries again. If it
*does* work, then it also cuts the distance in half and tries again.
The reason for cutting the distance in half in the failure case should be
obvious: you need to try a smaller distance, because the first try overshot.
The reason for cutting the distance in half in the success case might be
obvious to you, or it might not: it's because delta is half of the known gap
between a value known to be below or equal to the maximum, and the value
known to be above the maximum. First time through the loop, that's the y <=
max < y + y thing again.
Since the max value is less than y + y, you know for a fact that trying to
add delta one more time is going to fail (in the simplest case that is, you
simply have y + delta + delta = y + y, but even after you've been through
the loop once, adding whatever the current value of delta is twice will
always result in the net sum being y + y, so you never want to add delta
twice...halving it each time through is a way of ensuring that you don't).
Note that in some sense, the code you're asking about is simply finding the
individual bits that make up the maximum binary number allowed for the type.
The first loop finds the highest bit stored in the number, scanning through
the powers of two until it hits one that turns the number negative. The
second loop works its way backwards through the bits, adding each one that
will fit back in until you have the full maximum value allowed.
Note also that the code you're asking about (as well as many other samples
in this thread) is mostly theoretical. As has been mentioned, it makes a
lot more sense to simply note the built-in max value constants and use that
for a given type. Even if you didn't have those constants, it would be far
simpler to just check the size of the type and use predetermined knowledge
about the number representation for that type to come up with the
appropriate maximum value. Algorithmically determining the maximum value
for some type is essentially pointless for any built-in type (I suppose if
you're dealing with some abstracted numeric type that has nondeterministic
range restrictions, such an algorithm might be useful).
That said, I have some comments regarding the code you're asking about:
* Because we're dealing with binary numbers, the check for "y + delta >
0" before adding delta to y isn't needed. Perhaps this ties in with the
"abstracted numeric type" I posited above, but it doesn't apply to an "int",
for example.
* Also because the storage is a simple binary number -- that is,
assuming the maximum value is (2^N-1) for some N -- then the second loop is
a waste of time. Given that the code assumes that the type allows overflow
and it assumes that the storage is a straight binary representation, once
you've gotten to x being negative, you can find the maximum positive value
simply by subtracting 1 from x.
* I don't really like the condition for the while() in the second loop.
I believe that the loop is guaranteed to terminate, because of the way y is
calculated in the first loop. But it still strikes me as wrong to have a
loop in which the term that allows the loop to make forward progress can
eventually reach 0, but in which the loop condition does not test for that
case. That code in a slightly different context could easily wind up
looping infinitely. It's bad form, IMHO.
Pete
Just getting the basic algorithm out there