allow ffs & co. a binary search

[Richard Yao]

On 06/06/2015 08:13 PM, Erich Dollansky wrote:
> Hi,
> 
> I stumbled these days over the functions to find the first or last bit
> set. They are currently written like this:
> 
> /*
>  * Find First Set bit
>  */
> int
> ffs(int mask)
> {
> 	int bit;
> 
> 	if (mask == 0)
> 		return (0);
> 	for (bit = 1; !(mask & 1); bit++)
> 		mask = (unsigned int)mask >> 1;
> 	return (bit);
> }
> 
> With other words, the program loops until it finds what it searches for.
> 
> Why not do it the binary way?

The fastest portable way of calculating highest bit set is to use a
debrujin sequence:

https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

The binary approach is inferior, especially on Pentium 4 processors.

Just my two cents.

> 
>    int	res;
> 
> 	res	= 0;
> 	IF (Number != 0) THEN
> 		res	= 1;
> 		IF ((Number & 0xFFFFFFFF00000000) != 0) THEN
> 			Number	= Number & 0xFFFFFFFF00000000;
> 			res		= res + 32;
> 		END;
> 		IF ((Number & 0xFFFF0000FFFF0000) != 0) THEN
> 			Number	= Number & 0xFFFF0000FFFF0000;
> 			res		= res + 16;
> 		END;
> 		IF ((Number & 0xFF00FF00FF00FF00) != 0) THEN
> 			Number	= Number & 0xFF00FF00FF00FF00;
> 			res		= res + 8;
> 		END;
> 		IF ((Number & 0xF0F0F0F0F0F0F0F0) != 0) THEN
> 			Number	= Number & 0xF0F0F0F0F0F0F0F0;
> 			res		= res + 4;
> 		END;
> 		IF ((Number & 0xCCCCCCCCCCCCCCCC) != 0) THEN
> 			Number	= Number & 0xCCCCCCCCCCCCCCCC;
> 			res		= res + 2;
> 		END;
> 		IF ((Number & 0xAAAAAAAAAAAAAAAA) != 0) THEN
> 			Number	= Number & 0xAAAAAAAAAAAAAAAA;
> 			res		= res + 1;
> 		END;
> 	END;
> 	return res;
> 
> If you like the binary way I could give you the sources for the
> complete family following your style to replace the older functions.
> 
> Erich
> _______________________________________________
> freebsd-hackers at freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
> To unsubscribe, send any mail to "freebsd-hackers-unsubscribe at freebsd.org"
> 


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20150611/81ef3600/attachment.sig>