peterchen - 6 months ago 47

C Question

I am looking for an efficient way to determine the position of the least significant bit that is set in an integer, e.g. for 0x0FF0 it would be 4.

A trivial implementation is this:

`unsigned GetLowestBitPos(unsigned value)`

{

assert(value != 0); // handled separately

unsigned pos = 0;

while (!(value & 1))

{

value >>= 1;

++pos;

}

return pos;

}

Any ideas how to squeeze some cycles out of it?

(Note: this question is for people that enjoy such things, not for people to tell me xyzoptimization is evil.)

Answer

Bit Twiddling Hacks offers an excellent collection of, er, bit twiddling hacks, with performance/optimisation discussion attached. My favourite solution for your problem (from that site) is «multiply and lookup»:

```
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[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 = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
```

Helpful references:

- "Using de Bruijn Sequences to Index a 1 in a Computer Word" - Explanation about why the above code works.
- "Board Representation > Bitboards > BitScan" - Detailed analysis of this problem, with a particular focus on chess programming