[math-fun] min(x, y) and sorting without if(), mod without divide or if
On a 32-bit machine in C where x,y are ints, min(x,y) = y+(((x-y)>>31)&(x-y)); max(x,y) = x-(((x-y)>>31)&(x-y)); A related cute one is where you have X with 0<=X<M then you add some alteration to X which might move it into the interval [M, 2M) and we want to take the result mod M so as to return to the interval [0, M). Slow way: X = X%M. Faster way: if(X>=M) X -= M; no-if way: X -= ((M-1-X)>>31)&M; If X due to a subtractive alteration might have moved into [-M, 0) so to get it back you add M, if(X<0) X += M; no if-way: X += (X>>31)&M;
These (branch-avoiding) techniques are "well known", see (fxtbook) section 1.11 "Avoiding branches", pp.15ff where a warning of the form "Your compiler may be smarter than you thought" is given. A very good book about these tricks is "Hacker's Delight" (Henry S. Warren, Jr., Addison-Wesley, 2003). Also see the author's web site http://www.hackersdelight.org/ I always use if ( (unsigned)x > n ) as a replacement for if ( x<0 || x>n ) in a lot of combinatorial generators, often gaining substantial speedup. Only using sentinels tops this one (when applicable). See (fxtbook) p.174 for some practical considerations (I omitted the "fit things into a cache-line" here). cheers, jj * Warren Smith <warren.wds@gmail.com> [Jan 03. 2012 17:48]:
On a 32-bit machine in C where x,y are ints,
min(x,y) = y+(((x-y)>>31)&(x-y)); max(x,y) = x-(((x-y)>>31)&(x-y));
A related cute one is where you have X with 0<=X<M then you add some alteration to X which might move it into the interval [M, 2M) and we want to take the result mod M so as to return to the interval [0, M).
Slow way: X = X%M.
Faster way: if(X>=M) X -= M;
no-if way: X -= ((M-1-X)>>31)&M;
If X due to a subtractive alteration might have moved into [-M, 0) so to get it back you add M,
if(X<0) X += M;
no if-way: X += (X>>31)&M;
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Joerg Arndt -
Warren Smith