Originally Posted by
laserlight
I think we can stop discussing Snafuist's suggestion now as Snafuist has admitted that it is based on an unwarranted assumption.
But I don't think it actually is wrong. I think the description of it is wrong. Pass it any number, and it should produce the place of the first set bit. Try it. Set it up in a loop, and display the bits for that value, as well as the number it returns. Heck, I'll do it:
Code:
#include<stdio.h>
void printbit( unsigned char b )
{
printf( "%d%d%d%d%d%d%d%d ",
!!(b & 1), !!(b & 2),
!!(b & 4), !!(b & 8),
!!(b & 16), !!(b & 32),
!!(b & 64), !!(b & 128) );
}
int main ( void )
{
size_t counter;
unsigned int v = 0; /* 1 + 4 + 16 + 64; */
int r;
static const int debruijn[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
for( counter = 0; counter < 255; counter++ )
{
v = counter;
r = debruijn[((v & -v) * 0x077CB531UL) >> 27];
printf( "%d:" , r );
printbit( counter & 0xFF );
printf( "\n" );
if( counter % 8 == 7 )
getchar( );
}
return 0;
}
I don't think it's wrong, I think it's being misrepresented in its functionality, or how it should be used. I'm not seeing anything wrong with the way it's actually functioning. Pass it a number, it will tell you the place of the first set bit.
The only exception is if you pass it zero, which it returns zero for as well. So as long as you check your passed value to see if it is zero, you're fine.
Quzah.