Position of least significant bit that is set

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

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

There is an x86 assembly instruction (bsf) that will do it. :)

More optimized?!

Side Note:

Optimization at this level is inherently architecture dependent. Today's processors are too complex (in terms of branch prediction, cache misses, pipelining) that it's so hard to predict which code is executed faster on which architecture. Decreasing operations from 32 to 9 or things like that might even decrease the performance on some architectures. Optimized code on a single architecture might result in worse code in the other. I think you'd either optimize this for a specific CPU or leave it as it is and let the compiler to choose what it thinks it's better.

Most modern architectures will have some instruction for finding the position of the lowest set bit, or the highest set bit, or counting the number of leading zeroes etc.

If you have any one instruction of this class you can cheaply emulate the others.

Take a moment to work through it on paper and realise that x & (x-1) will clear the lowest set bit in x, and ( x & ~(x-1) ) will return just the lowest set bit, irrespective of achitecture, word length etc. Knowing this, it is trivial to use hardware count-leading-zeroes / highest-set-bit to find the lowest set bit if there is no explicit instruction to do so.

If there is no relevant hardware support at all, the multiply-and-lookup implementation of count-leading-zeroes given here or one of the ones on the Bit Twiddling Hacks page can trivially be converted to give lowest set bit using the above identities and has the advantage of being branchless.

The fastest (non-intrinsic/non-assembler) solution to this is to find the lowest-byte and then use that byte in a 256-entry lookup table. This gives you a worst-case performance of four conditional instructions and a best-case of 1. Not only is this the least amount of instructions, but the least amount of branches which is super-important on modern hardware.

Your table (256 8-bit entries) should contain the index of the LSB for each number in the range 0-255. You check each byte of your value and find the lowest non-zero byte, then use this value to lookup the real index.

This does require 256-bytes of memory, but if the speed of this function is so important then that 256-bytes is well worth it,

E.g.

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}

Inspired by this similar post that involves searching for a set bit, I offer the following:

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; 
}

Pros:

• no loops
• no branching
• runs in constant time
• handles value=0 by returning an otherwise-out-of-bounds result
• only two lines of code

Cons:

• assumes little endianness as coded (can be fixed by changing the constants)
• assumes that double is a real*8 IEEE float (IEEE 754)

Update: As pointed out in the comments, a union is a cleaner implementation (for C, at least) and would look like:

unsigned GetLowestBitPos(unsigned value)
{
    union {
        int i[2];
        double d;
    } temp = { .d = value ^ (value - !!value) };
    return (temp.i[1] >> 20) - 1023;
}

This assumes 32-bit ints with little-endian storage for everything (think x86 processors).

After 11 years we finally have countr_zero!

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>
 
int main()
{
    for (const std::uint8_t i : { 0, 0b11111111, 0b00011100, 0b00011101 }) {
        std::cout << "countr_zero( " << std::bitset<8>(i) << " ) = "
                  << std::countr_zero(i) << '\n';
    }
}

Well done C++20

It can be done with a worst case of less than 32 operations:

Principle: Checking for 2 or more bits is just as efficient as checking for 1 bit.

So for example there's nothing stopping you from checking for which grouping its in first, then checking each bit from smallest to biggest in that group.

So...
if you check 2 bits at a time you have in the worst case (Nbits/2) + 1 checks total.
if you check 3 bits at a time you have in the worst case (Nbits/3) + 2 checks total.
...

Optimal would be to check in groups of 4. Which would require in the worst case 11 operations instead of your 32.

The best case goes from your algorithms's 1 check though to 2 checks if you use this grouping idea. But that extra 1 check in best case is worth it for the worst case savings.

Note: I write it out in full instead of using a loop because it's more efficient that way.

int getLowestBitPos(unsigned int value)
{
    //Group 1: Bits 0-3
    if(value&0xf)
    {
        if(value&0x1)
            return 0;
        else if(value&0x2)
            return 1;
        else if(value&0x4)
            return 2;
        else
            return 3;
    }

    //Group 2: Bits 4-7
    if(value&0xf0)
    {
        if(value&0x10)
            return 4;
        else if(value&0x20)
            return 5;
        else if(value&0x40)
            return 6;
        else
            return 7;
    }

    //Group 3: Bits 8-11
    if(value&0xf00)
    {
        if(value&0x100)
            return 8;
        else if(value&0x200)
            return 9;
        else if(value&0x400)
            return 10;
        else
            return 11;
    }

    //Group 4: Bits 12-15
    if(value&0xf000)
    {
        if(value&0x1000)
            return 12;
        else if(value&0x2000)
            return 13;
        else if(value&0x4000)
            return 14;
        else
            return 15;
    }

    //Group 5: Bits 16-19
    if(value&0xf0000)
    {
        if(value&0x10000)
            return 16;
        else if(value&0x20000)
            return 17;
        else if(value&0x40000)
            return 18;
        else
            return 19;
    }

    //Group 6: Bits 20-23
    if(value&0xf00000)
    {
        if(value&0x100000)
            return 20;
        else if(value&0x200000)
            return 21;
        else if(value&0x400000)
            return 22;
        else
            return 23;
    }

    //Group 7: Bits 24-27
    if(value&0xf000000)
    {
        if(value&0x1000000)
            return 24;
        else if(value&0x2000000)
            return 25;
        else if(value&0x4000000)
            return 26;
        else
            return 27;
    }

    //Group 8: Bits 28-31
    if(value&0xf0000000)
    {
        if(value&0x10000000)
            return 28;
        else if(value&0x20000000)
            return 29;
        else if(value&0x40000000)
            return 30;
        else
            return 31;
    }

    return -1;
}

Why not use binary search? This will always complete after 5 operations (assuming int size of 4 bytes):

if (0x0000FFFF & value) {
    if (0x000000FF & value) {
        if (0x0000000F & value) {
            if (0x00000003 & value) {
                if (0x00000001 & value) {
                    return 1;
                } else {
                    return 2;
                }
            } else {
                if (0x0000004 & value) {
                    return 3;
                } else {
                    return 4;
                }
            }
        } else { ...
    } else { ...
} else { ...

You could check if any of the lower order bits are set. If so then look at the lower order of the remaining bits. e.g.,:

32bit int - check if any of the first 16 are set. If so, check if any of the first 8 are set. if so, ....

if not, check if any of the upper 16 are set..

Essentially it's binary search.

unsigned GetLowestBitPos(unsigned value)
{
    if (value & 1) return 1;
    if (value & 2) return 2;
    if (value & 4) return 3;
    if (value & 8) return 4;
    if (value & 16) return 5;
    if (value & 32) return 6;
    if (value & 64) return 7;
    if (value & 128) return 8;
    if (value & 256) return 9;
    if (value & 512) return 10;
    if (value & 1024) return 11;
    if (value & 2048) return 12;
    if (value & 4096) return 13;
    if (value & 8192) return 14;
    if (value & 16384) return 15;
    if (value & 32768) return 16;
    if (value & 65536) return 17;
    if (value & 131072) return 18;
    if (value & 262144) return 19;
    if (value & 524288) return 20;
    if (value & 1048576) return 21;
    if (value & 2097152) return 22;
    if (value & 4194304) return 23;
    if (value & 8388608) return 24;
    if (value & 16777216) return 25;
    if (value & 33554432) return 26;
    if (value & 67108864) return 27;
    if (value & 134217728) return 28;
    if (value & 268435456) return 29;
    if (value & 536870912) return 30;
    if (value & 1073741824) return 31;
    return 0; // no bits set
}

50% of all numbers will return on the first line of code.

75% of all numbers will return on the first 2 lines of code.

87% of all numbers will return in the first 3 lines of code.

94% of all numbers will return in the first 4 lines of code.

97% of all numbers will return in the first 5 lines of code.

etc.

This unrolled "loop" will be quicker for 97% of the test cases than most of the algorithms posted in this thread!

I think people that are complaining on how inefficient the worst case scenario for this code don't understand how rare that condition will happen.

See my answer here for how to do it with a single x86 instruction, except that to find the least significant set bit you'll want the BSF ("bit scan forward") instruction instead of BSR described there.

Here is one simple alternative, even though finding logs is a bit costly.

if(n == 0)
  return 0;
return log2(n & -n)+1;   //Assuming the bit index starts from 1

If you have the resources, you can sacrifice memory in order to improve the speed:

static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };

unsigned GetLowestBitPos(unsigned value)
{
    assert(value != 0); // handled separately
    return bitPositions[value];
}

Note: This table would consume at least 4 GB (16 GB if we leave the return type as unsigned). This is an example of trading one limited resource (RAM) for another (execution speed).

If your function needs to remain portable and run as fast as possible at any cost, this would be the way to go. In most real-world applications, a 4GB table is unrealistic.