first 1 in a bitmask using log2

Question

I am trying to get the last 1 in a bitmask. More mathematically speaking, I have a number k, that can be written in its binary form as a sequence of 1 and 0. I want the "weight" or "index" of the last 1 in that number (from the right).

As an example, for the number 0b 10 0100 (36 in decimal), I want to get 3 (because the rightmost 1 is on 3rd position from the right)

I can find the first 1 easily (in my case 6), as the size of the number, or its base-2 log (rounded down +1), but what about the last one?

For information, I will use this in a dirty trick in MS Excel, described in https://stackoverflow.com/questions/5065432/excel-find-last-value-in-an-array/11246728#11246728

Answer 1

If $x$ is your original number, (~x + 1) & x will have only one bit set, the same as the least significant set bit of $x$. For example, if $x$ is 10101000, then (~x + 1) & x = 00001000. Perhaps that helps? You can then use a lookup table, or one of the techniques in Which bit is set to figure out which bit is still set.

You might also look at the references given the the OEIS entry for this function.