🚀 go-pugleaf

In article <BsFMD4.HAI@watcgl.uwaterloo.ca> awpaeth@watpix.waterloo.edu (Alan Wm Paeth) writes:
>An elegant and efficient MSB-finding algorithm has been forwarded to me by
>Dean Inada (dmi@peregrine.com). It has a constant running time proportional
>to Log2(machine int size):

This is a good example of 

1.  Why the instruction is needed as hardware, if it is important at all;

2.  Why condition codes should be user-available.


Now check the number of operations.  Assuming that all the constants are in
registers, and there is total inlining, we have at least 9 arithmetic
operations of the same type (&) one zeroing, and 5 conditional adds.  This
is very definitily slow; if the operation is needed that rarely, a crude
algorithm is probably almost as good as far as total time goes.

Now the conditional operations can be eliminated if a condition bit can be
introduced into an arithmetic register.  If we take a true statement to be
1, then the above algorithm would be better as 

msbpos(i)
    {
    int p;
    p = (i & 0xFFFF0000  >  0 /* 0x0000xxxx */ ) ;
    (p <<= 1) += (i & 0xFF00FF00  >  i &  0x00ff00ff    ) ;
    (p <<= 1) += (i & 0xF0F0F0F0  >  i &  0x0f0f0f0f    ) ;
    (p <<= 1) += (i & 0xCCCCCCCC  >  i &  0x33333333    ) ;
    (p <<= 1) += (i & 0xAAAAAAAA  >  i &  0x55555555    ) ;
    return(;

This has a few more instructions, but no conditional operations.


-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)