Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!ima!mirror!cca!g-rh
From: g-rh@cca.UUCP (Richard Harter)
Newsgroups: comp.lang.c
Subject: Re: Finding MSB in bit string
Message-ID: <11053@cca.UUCP>
Date: Tue, 11-Nov-86 21:43:13 EST
Article-I.D.: cca.11053
Posted: Tue Nov 11 21:43:13 1986
Date-Received: Wed, 12-Nov-86 06:32:22 EST
References: <800@oakhill.UUCP>
Reply-To: g-rh@cca.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge
Lines: 69

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 :-)