Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!mcvax!guido
From: guido@mcvax.uucp (Guido van Rossum)
Newsgroups: comp.lang.c
Subject: Re: Finding MSB in bit string
Message-ID: <7143@boring.mcvax.UUCP>
Date: Thu, 13-Nov-86 15:52:36 EST
Article-I.D.: boring.7143
Posted: Thu Nov 13 15:52:36 1986
Date-Received: Thu, 13-Nov-86 21:55:29 EST
References: <800@oakhill.UUCP> <11053@cca.UUCP>
Reply-To: guido@boring.uucp (Guido van Rossum)
Organization: "Stamp Out BASIC" Committee, CWI, Amsterdam
Lines: 19
Apparently-To: rnews@mcvax


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