allow ffs & co. a binary search
Erich Dollansky
erichsfreebsdlist at alogt.com
Sun Jun 7 00:13:27 UTC 2015
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?
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
More information about the freebsd-hackers
mailing list