Finding MSB in bit string

[Guido van Rossum]

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 at mcvax.uucp>