# Position of least significant bit that is set

### 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.)

 Thanks everyone for the ideas! I've learnt a few other things, too. Cool!

1
105
4/20/2009 8:00:17 AM

### Accepted 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:

160
4/28/2019 11:01:50 PM

Why not use the built-in ffs? (I grabbed a man page from Linux, but it's more widely available than that.)

## ffs(3) - Linux man page

### Name

ffs - find first bit set in a word

### Synopsis

``````#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);
``````

### Description

The ffs() function returns the position of the first (least significant) bit set in the word i. The least significant bit is position 1 and the most significant position e.g. 32 or 64. The functions ffsll() and ffsl() do the same but take arguments of possibly different size.

### Return Value

These functions return the position of the first bit set, or 0 if no bits are set in i.

### Conforming to

4.3BSD, POSIX.1-2001.

### Notes

BSD systems have a prototype in `<string.h>`.

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon