Find the lowest set bit

Question

I have 5 bit numbers like

10000
01000
00100

If only one bit is on in my calculation i have no problem.

but if 2 bits are on then I want to select only the first on bit for example

10010

i want to treat it as 2 instead of the number 18

is there any bitwise operation which may i use in such sitution?

Answer 1

Since you only want to isolate it, not get its index, it's easy:

function firstSetBit(number)
{
    return number & -number;
}

It works because of the binary representation of -number, which is called "two's complement".

To get a better example, let's say the number is 888, which is 0000001101111000 in binary. The leading zeroes make a 16 bit number, but this works with any integer size.

To obtain the two's complement of a number, we first complement it, setting all 1s to 0s and 0s to 1s.

          number: 0000001101111000
      complement: 1111110010000111

Then we add 1 to it.

          number: 0000001101111000
      complement: 1111110010000111
           add 1: 1111110010001000

Note that if the rightmost bit is 1, this would create a carry which flips all 1s into 0s until a 0 is reached.

This number is now actually also the binary representation of -number.

          number: 0000001101111000
      complement: 1111110010000111
           add 1: 1111110010001000
         -number: 1111110010001000

We now take the bitwise & of number and -number.

          number: 0000001101111000
         -number: 1111110010001000
number & -number: 0000000000001000

To the right of the target bit, number is all 0s by premise. -number is also all 0s because they got flipped during the +1. Bitwise AND of 0 and 0 produces 0.

At the target bit, number has a 1, also by premise. -number also has a 1 because of the negate turning it into a 0 and carry putting it back to 1. Bitwise AND of 1 and 1 produces 1.

To the left of the target bit, number and -number always form 0 and 1 pairs because it is undisturbed by the +1 step of the two's complement procedure. Bitwise AND of 1 and 0 produces 0.

And thus, we have shown that number & -number produces the lowest 1 bit of the number.