Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 http://stackoverflow.com/questions/5065432/excel-find-last-value-in-an-array/11246728#11246728

share|improve this question
1  
A straightforward but not particularly nice solution is to divide repeatedly by $2$ until you get a non-integer; the number of divisions is the desired result. –  Brian M. Scott Jun 28 '12 at 14:53
    
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. –  Henning Makholm Jun 28 '12 at 15:10
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
1  
Of course, in 2's complement arithmetic (~x + 1) is simply -x. –  Henning Makholm Jun 28 '12 at 15:17
    
Great answer. Still have to port those operators to MS Excel, of course... –  PPC Jun 28 '12 at 19:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.