How to find index of first set bit

Question

Is there bitwise solution to find the index of first set bit in mask with only one bit set? e.g. for 8 it would be 3, for 16 => 4 and so on. No loops plz. The best solution I can come up with is to createa map of bit to index.

`No loops plz` - I love seeing that kind of stipulation. Why do you dislike loops? — Ian, Aug 08 '13 at 20:01

score 5 · Accepted Answer · answered Aug 08 '13 at 20:09

5

function firstBit(x) {
    return Math.floor(
        Math.log(x | 0) / Math.log(2)
    ) + 1;
}
i=4; console.log(i.toString(2), firstBit(i)); // 100 3
i=7; console.log(i.toString(2), firstBit(i)); // 111 3
i=8; console.log(i.toString(2), firstBit(i)); // 1000 4

answered Aug 08 '13 at 20:09

Paul S.

64,864
9
122
138

1

This is assuming `x.toString(2).length` won't float your boat – Paul S. Aug 08 '13 at 20:15
1

Great! Thanks a lot!) I guess Math.floor is used only for cases when multiple bits are set? – Denis Narushevich Aug 08 '13 at 20:16
Yep. I added `1` to them so it matched with _length_, if you dont want that you can remove it, and `firstBit(0)` is `-Infinity` (because it doesn't have one!). The `x | 0` casts `x` to a _32-bit integer_ – Paul S. Aug 08 '13 at 20:20
Math.floor(value)+1 can be replaced by (value | 0)+1 – Denis Narushevich Aug 08 '13 at 20:26
@DenisNarushevich Yep, it would change edge cases though (`0`). Just use whatever suits your needs! – Paul S. Aug 08 '13 at 20:28

score 3 · Answer 2 · answered Mar 21 '17 at 23:30

3

For posterity, ES6 introduced Math.log2 (and also log10) which does exactly that:

Math.log2(8) === 3

As a reminder, logA(x) is logB(x) / logB(A) for any A and B

answered Mar 21 '17 at 23:30

floribon

19,175
5
54
66

`Math.floor(Math.log2(n))` works for any number. – Míng Aug 24 '21 at 07:32

How to find index of first set bit

2 Answers2

Linked