why left+(right-left)/2 will not overflow? -


in article: http://googleresearch.blogspot.sg/2006/06/extra-extra-read-all-about-it-nearly.html, mentioned quick sort algorithm had bug (left+right)/2, , pointed out solution using left+(right-left)/2 instead of (left+right)/2. solution given in question bug in quicksort example (k&r c book)?

my question why left+(right-left)/2 can avoid overflow? how prove it? in advance.

you have left < right definition.

as consequence, right - left > 0, , furthermore left + (right - left) = right (follows basic algebra).

and consequently left + (right - left) / 2 <= right. no overflow can happen since every step of operation bounded value of right.


by contrast, consider buggy expression, (left + right) / 2. left + right >= right, , since don’t know values of left , right, it’s entirely possible that value overflows.


Comments

Popular posts from this blog

matlab - "Contour not rendered for non-finite ZData" -

delphi - Indy UDP Read Contents of Adata -

javascript - Any ideas when Firefox is likely to implement lengthAdjust and textLength? -