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

Post a Comment

Popular posts from this blog

android - Hide only the Action bar on Scroll not action bar tabs -

-
Image
i getting issue @ trying hide action bar while scrolling down.then while scrolling up,the action bar have shown again. for eg: i referred tutorial .here can see output , respective codes related hide , show action bar. i showing output till now. after scrolling down: the screenshot above shown, hide action bar tab also.but have hide action bar.that's major issue. after scrolling up: the screenshot above shows displays action bar tabs. topratedfragment.java: import info.androidhive.tabsswipe.r; import android.app.actionbar; import android.content.res.typedarray; import android.os.bundle; import android.support.v4.app.fragment; import android.view.layoutinflater; import android.view.view; import android.view.viewgroup; import android.view.viewtreeobserver; import android.view.window; import android.widget.scrollview; public class topratedfragment extends fragment implements viewtreeobserver.onscrollchangedlistener { private float mactionbarheight; ...
Read more

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

-
i'm trying plot frequency characteristic equation using ezplot, matlab gives following warning, "contour not rendered non-finite zdata". have used command plot frequency equations warning , plot display empty , not change axis range well. can please help. appreciated. here's code i'm using. % transfer matrix case-i, thin rotor clear all; clc; ei = 1626; l = 0.15; m = 0.44108; = 2.178*10^-4; i_p = 2.205*10^-5; itr = 0.24; i_pr = 0.479; syms p n; f = [1 l*1i l^2/(2*ei)*1i l^3/(6*ei); 0 1 l/ei -l^2/(2*ei)*1i; 0 0 1 -l*1i; 0 0 0 l]; p = [ 1 0 0 0; 0 1 0 0; 0 -it*p^2+i_p*n*p 1 0; -m*p^2 0 0 1]; p_r = [1 0 0 0; 0 1 0 0; 0 -itr*p^2+i_pr*n*p 1 0; -m*p^2 0 0 1]; = f*p*f*p*f*p*f; b = p_r*f*p*f*p*f; r = a(1,2)/a(1,4); a12_p = 0; a22_p = a(2,2)-r*a(2,4); a32_p = a(3,2)-r*a(3,4); a42_p = a(4,2)-r*a(4,4); ap(2,2) = a22_p; ap(3,2) = a32_p; ap(4,2) = a42_p; ap(4,4) = 1; c = b*ap; m = [c(3,2) c(3,4); c(4,2) c(4,...
Read more

delphi - Indy UDP Read Contents of Adata -

-
i using indy udp server read string of data. however, not know how work adata parameter. can around converting binary using bytetobin function below , convert hex using bintohex1 . feel stupid , works slow. know how can directly results without 2 conversions? thanks!! here codes: procedure tform1.idudpserver1udpread(athread: tidudplistenerthread; const adata: tidbytes; abinding: tidsockethandle); var buf: tidbytes; buffer: string; data_received: string; begin if bytestostring(adata) <> 'hello' begin buffer := hextostring('00'); setlength(buf, length(buffer)); copytidstring(buffer, buf, 0); abinding.sendto(abinding.peerip, abinding.peerport, buf); data_received := bintohex1(bytetobin(adata[1]) + bytetobin(adata[2]) + bytetobin(adata[3]) + bytetobin(adata[4]) + bytetobin(adata[5]) + bytetobin(adata[6]) + bytetobin(adata[7]) + bytetobin(adata[8]) + bytetobin(adata[9]) + bytetobin(adata[10]) + bytetobin(adata[11...
Read more