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?

Rod

Binary numbers are read with values increasing right to left, like decimal numbers - 10010 is 18, not 9. Just to be clear, you're asking for the lowest set bit, yes? – Chadchadabe

Sorry for the false description. And what I need it the lowest set bit. How may I do this? – Rod

I've tweaked the question title + example to match what I think you meant. – Chadchadabe

Well I don't know how this works in JS, but in say C# I'd do x & -x to isolate the lowest bit. edit: tried it, works in JS too. – Gaunt

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.

Gaunt

Nice one, worthy of a spot in graphics.stanford.edu/~seander/bithacks.html ! (I don't think it's mentioned there?) – Chadchadabe

I was thinking about this, and depending upon how the unary operator - is implemented, number - (number & (number - 1)) might be more efficient. Uses the same principle. – Lobster

@Lobster I don't really see why the JS compiler would implement negation in a silly way.. – Gaunt

@harold I think that all numbers in javascript are floating point. – Lobster

@Lobster well they were, but the new JS engines do type inference, right? – Gaunt

@harold ah, ok, did not realize. Your solution should be fine then. – Lobster

@Lobster Your function doesn't isolate the lowest set bit, it clears it. E.g. 3 & (3 - 1) = 2. – Eureka

Answer 2

return log2(n & -n) + 1;

this will may help you.

Ewart

You can always edit your post and add code formatting. – Nucleus

Please describe in your answer, what was the problem, and how will this snippet solve it, to help others understand this answer – Lapboard

Answer 3

Binary operators usually affect all bits of a number. So, there is no special function to get only the first "1" in number. But you can try such a function:

function filterFirstFoundBit(number)
{
    for (var i = 0; i < 32; i++) {
        if ((1 << i) & number)
        {
            return 1 << i;
        }
    }
    return number;
}
document.write(filterFirstFoundBit(9)); //10010​​​​​​​​

Try it here

Xochitlxp

Answer 4

function isolateLowestBit(input)
{
  mask = 1;
  while (mask <= input)
  {
    if (mask & input)
    {
      // found match - mask is set to the value of the lowest bit
      return mask;
    }

    mask *= 2;  // shift up mask by one bit
  }

  // no match
  return 0;
}

Beware that bitwise operations in Javascript are a bad idea, since since Javascript numbers aren't naturally integer.

Chadchadabe