[comp.lang.c] Finding MSB in bit string

guido@mcvax.uucp (Guido van Rossum) (11/10/86)

Tom, I assume you want maximum speed (see your motto).   All the fast
solutions are going to take quite some memory.  But so does your LSB
solution: it is a "sparse" switch, so the compiler can't use a jump
table but has to generate a lot of comparisons.  I hope the average C
compiler generates "binary search" code like ours (4.3BSD); 32
comparisons in a row might be slower than a loop with shifts!  Anyway,
here's my solution (untested).

Use a similar trick as used to count the number of one bits: first find
the highest nonzero byte, then use a table with 256 entries.

msb(t)
	unsigned long t;
{
	static char tab[256]= {
		-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
		... /* Ahh, you can fill this in for yourself */
	};
	/* What's a better value for entry 0?  What's the int of 0? */

	if (t & 0xff000000)
		return tab[t>>24];
	else if (t & 0xff0000)
		return tab[(t>>16) & 0xff];
	else if (t & 0xff00)
		return tab[(t>>8) & 0xff];
	else
		return tab[t & 0xff];
}

Variations:
	- use a loop instead of 4 times if/then/else;
	- pack the table in 128 bytes (it's only 3 bits of data per
	  entry if you don't count the entry for 0)
	- use a smaller table and a longer loop
	- cast t to a 4-byte char array to extract the right byte
	  (but this requires different code for a big-endian machine
	  than for a little-endian, while the code here works for any
	  machine with at most 32 bits per long int.)
-- 
	Guido van Rossum, CWI, Amsterdam <guido@mcvax.uucp>

guido@mcvax.uucp (Guido van Rossum) (11/10/86)

In article <7135@boring.mcvax.UUCP> I wrote:
>	/* What's a better value for entry 0?  What's the int of 0? */

I meant: What's the MSB of 0?

zben@umd5 (Ben Cranston) (11/10/86)

In article <800@oakhill.UUCP> tomc@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"

g-rh@cca.UUCP (Richard Harter) (11/12/86)

Tom asked about fast ways to find the msb and asked if there was a
trick analogous to the two's complement trick for the lsb.  Here a
handful of ways:

On the LSB trick:  Do a one's complement and add one (which can be done
in C in a machine independent way) rather than assuming that that
negation is two's complement.

On getting the MSB:  If you're not into portability and your machine
has floating point hardware float the integer in question; the exponent
will have the msb (plus an offset).  Mask it off and extract it.  This
is probably fastest if you have the right hardware.

Another method:  Array of 32 ints = {1,2,4,8,...}.  Do a binary search
and compare, e.g.

	msb=16;
	step=8;
	for (i=0;i<5;i++) {
	  if (x>a[msb]) msb += step;
	  else if (x<a[msb]) msb -= step;
	  else break;
	  step /= 2;
	  }

[Warning -- above code not tested and probably wrong on boundary conditions.]

Another method:  Use array of 5 masks:

	unsigned long mask[5] = {
	  0xffff000, 0xff00ff00, 0xf0f0f0f0, 0xeeeeeeee, 0xaaaaaaaa
	  };

	msb = 0;
	step = 16;
	y = x;
	for (i=0;i<5;i++) {
	  if (y & mask[i]) {
	    y &= mask[i];
	    msb += step;
	    }
	  step /= 2;
          }

Again, no claims for correctness of code.  The general idea is that the
masks represent a defacto binary search for the msb.  The cute thing about
this is that you can do the lsb in an analogous way.

Finally, for machine independence consider the following:

	test = 1;
	msb = 0;
	while (x>test) {
	  test = 2*test +1;
	  msb++;
	  }


So there you are, that's four different methods, none of them using shifts,
all of them reasonably efficient.  What's wrong with shifts anyway?
Oh yes, what is the MSB of 0?

Here's another one -- suppose you want the number of 1's in a bit string.
What's a good general method?  How would a real programmer do it?

-- 

Richard Harter, SMDS Inc. [Disclaimers not permitted by company policy.]
	For Cheryl :-)

guido@mcvax.uucp (Guido van Rossum) (11/13/86)

In article <11053@cca.UUCP> g-rh@cca.UUCP (Richard Harter) writes:
>Oh yes, what is the MSB of 0?

This should cause an exception like 1/0 does.  If msb(x) is defined as
floor(2 log x), then it isn't defined for x==0.

>Here's another one -- suppose you want the number of 1's in a bit string.
>What's a good general method?  How would a real programmer do it?

This has been discussed in this group a while ago.  It goes something like

	return count[x&0xff] + count[(x>>8)&0xff] +
		count[(x>>16)&0xff] + count[(x>>32)&0xff;

where count is a 256-byte array of precomputed values.  Of course you
could use a smaller array and add more values, possibly in a loop.

(I hope this time I didn't forget some offsets like in my solution of
the MSB problem.)

tiemann@mcc-pp.UUCP (Michael Tiemann) (11/14/86)

In article <7143@boring.mcvax.UUCP>, guido@mcvax.uucp (Guido van Rossum) writes:
> >What's a good general method?  How would a real programmer do it?
> 
> This has been discussed in this group a while ago.  It goes something like
> 
> 	return count[x&0xff] + count[(x>>8)&0xff] +
> 		count[(x>>16)&0xff] + count[(x>>32)&0xff;
						^^
						24
> 
> (I hope this time I didn't forget some offsets like in my solution of
> the MSB problem.)

Nope, just some arithmetic.

How about

	cnt = count[x&0xff];
	cnt += count[(x>>=8) & 0xff];
	cnt += count[(x>>=8) & 0xff];
	return	cnt + count[x&0xff];

for those poor souls without barrel shifters.

But this is not a *general* method, since there is no parameterization
of the bit-string (!). Not all bit-strings are 32-bit ints. I won't
*even* touch the issue of bit-string alignment...

Michael
tiemann@mcc.com

rlk@chinet.UUCP (Richard Klappal) (11/15/86)

I don't remember the beginning of the discussion, and its expired
here, but whats wrong with

	msb = 1 << sizeof(object);
	extracted_bit = object & msb;


-- 
---
UUCP: ..!ihnp4!chinet!uklpl!rlk || MCIMail: rklappal || Compuserve: 74106,1021
      ..!ihnp4!ihu1h!rlk
---