Finding MSB in bit string

[Ben Cranston]

In article <800 at oakhill.UUCP> tomc at oakhill.UUCP (Tom Cunningham) writes:

> ...  Finding the LSB in this way is no problem:
>	unsigned i, t;
>	t = -i;
>	i &= t;
>	switch (i) {
>	case 1:
>	case 2:
>       ...
>	}

Isn't this highly dependant on having a two's compliment machine?  On my
one's compliment machine the "and" would always return zero...

>Any equivalent way to do this to get the MSB?

My machine has an extensive "search" instruction set.  It could find the
MSB of a 36 bit integer word in 36 cycles (plus setup) by applying a
"search less than or equal" instruction to a list of 36 constants of the
same form as your switch statement: 1,2,4,8,16..2**30 .

Of course, there is also a "load shift and count" instruction that loads
a word, then shifts it left until the top two bits differ, returning you
both the shift count and the resulting word.  That would do it even faster.

Of course, there is no way to make a higher-level language generate this
kind of code, so if I were silly enough to use a higher-level language I
would have to make a library routine to do it.  I would suggest that you
do this also.  This way you could have an efficient implementation on
each different machine you must support.
-- 
                    umd5.UUCP    <= {seismo!umcp-cs,ihnp4!rlgvax}!cvl!umd5!zben
Ben Cranston zben @ umd2.UMD.EDU    Kingdom of Merryland Sperrows 1100/92
                    umd2.BITNET     "via HASP with RSCS"