Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!husc6!seismo!mcvax!guido
From: guido@mcvax.uucp (Guido van Rossum)
Newsgroups: comp.lang.c
Subject: Re: Finding MSB in bit string
Message-ID: <7135@boring.mcvax.UUCP>
Date: Sun, 9-Nov-86 17:15:49 EST
Article-I.D.: boring.7135
Posted: Sun Nov  9 17:15:49 1986
Date-Received: Mon, 10-Nov-86 06:12:16 EST
References: <800@oakhill.UUCP>
Reply-To: guido@boring.uucp (Guido van Rossum)
Organization: "Stamp Out BASIC" Committee, CWI, Amsterdam
Lines: 41
Apparently-To: rnews@mcvax

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>