I have code, which works, to find the most significant bit set in an unsigned
int. It's an ffs clone for systems without the non-standard libc ffs().
Our other "bit" code uses bit twiddling and is fast. This one algorithm is
about 300% slower. It's also slow on the boxes that do have it as part the math library
version from libc.
Since ffs is part of libc on only some of our boxes, and we need it everywhere, I
reverse engineered it and got:
Code:
int
ffs(unsigned int value)
int exponent=floor(log2((double) value));
return exponent+1;
}
After googling I got, among other things (from D Neto) some
promising code, or so it seemed.
Code:
ffs1(register unsigned int value)
{
int i=0;
value |= value>>1;
value |= value>>2;
value |= value>>4;
value |= value>>8;
value |= value>>16;
value ^= (value>>1);
while(value)
{
value=value>>1;
i++;
}
return i;
}
Another try by me:
Code:
int ffs2(register unsigned int value){
register int i=0;
if(value)
for(i=1;~value&1;value=value>>1,++i);
return i;
}
Profile says for 104,000,000 iterations ffs1() was 35% slower the ffs with math.
ffs2() is about 5% faster than ffs() for the same test. -- not really significant.
What am I missing?
ffs() is part of the critical path in new code and needs improvement. Suggestions,
changes, other algorithms?
Thanks.