Originally Posted by
MK27
That is certainly an interesting idea, but I'd kind of like to see how you think this will not be the slowest method?
Computing the number of trailing zeros takes exactly 5 operations (independent of the size of the input number). Consider the following code (for computing the NTZ in 32 bits)
Code:
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
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
};
r = debruijn[((v & -v) * 0x077CB531UL) >> 27];
The 5 operations are:
- bitwise AND
- subtraction
- multiplication
- bitshift
- array lookup
Can you do it in less than 5 ops?
Greets,
Philip