0
$\begingroup$

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

  • 0
    If you have a reasonably conventional set of bitwise operators available, you can isolate the last bit using `x AND NOT (x-1)`. But you might need to use logarithms to find its position.2012-06-28

1 Answers 1

2

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.

  • 0
    Great answer. Still have to port those operators to MS Excel, of course...2012-06-28