Index of second least significant set bit

Question

How can you get the index of the second least significant bit? For example if x=136 this should be 8 (using 1-indexing).

The indexing is from the least significant bit. For example:

bin(136)
'0b10001000'

If x=88 the output should be 5.

To make this work properly we also need a test that the number of bits set is at least 2. Luckily bin(x).count('1') will do that.

There are answers for finding the least significant bit at return index of least significant bit in Python (although at least one of the answers seems to be wrong).

how does this work? e.g. `(1 + (0x88 ^ 0x87)) >> 1` == `8`. While, it should be 4. i think i'm missing something. — Corley Brigman, Feb 11 '14 at 16:24
@CorleyBrigman Oh thank you! It seems it didn't work. Fixed question. — marshall, Feb 11 '14 at 16:28
it seems what you really want is something like `len(bin(x ^ (x-1))) - 2`, which gives the correct value of 4 for 0x88 (which is the correct value), and should work for other values as well. it involves a string cast, which is going to be slower i guess, but in python, it might not make much difference. — Corley Brigman, Feb 11 '14 at 16:29
that answer doesn't return the _index_, it returns the _lowest power of 2_. which means that in `10001000`, you want it to return `4` - the index of the lowest bit. it actually returns `1000` - the _value_ of that lowest bit, which you then have to take the log(2) of someway. — Corley Brigman, Feb 11 '14 at 16:31
@CorleyBrigman bin(88) = '0b1011000' so the second least significant bit is at index 5 from the right, starting at 1. — marshall, Feb 11 '14 at 16:35
confused 88 with 0x88. you are correct, for the second set LSB for 88. — Corley Brigman, Feb 11 '14 at 16:41

score 2 · Answer 1 · edited May 23 '17 at 12:26

2

Mask off the least significant bit, then find the least significant bit.

Borrowing from my answer to the other question:

def fss(x):
    """Returns the index, counting from 1, of the
    second least significant set bit in `x`.
    """
    x = x & (x-1)
    return (x&-x).bit_length()

edited May 23 '17 at 12:26

Community

1
1

answered Aug 31 '16 at 10:47

David Jones

4,766
3
32
45

lejlot · Answer 2 · 2014-02-11T16:33:04.837

1

if you can get the least significant position, simply remove it from the variable and apply once again the same reasoning.

get_least( x - ( 1 << get_least(x) ) )

(assuming get_least returns 0 indexed bit numbers)

or in functional form

def get_least(x):
  return ...........

def get_second_least(x):
  return get_least( x - ( 1 << ( get_least(x) ) ) )

edited Feb 11 '14 at 16:33

answered Feb 11 '14 at 16:11

lejlot

64,777
8
131
164

corrected mistakes - instead of xor, and (least-1), as your method returns 1 indexed bit numbers. Now it should work fine. – lejlot Feb 11 '14 at 16:18

score 1 · Answer 3 · answered Feb 11 '14 at 17:10

You could iterate over the bits from lsb to msb. You can also use this to get the nth least bit.

def get_nth_least_bit(x, n):
    sum = 0
    for i in range(0,x.bit_length()):
        sum += (x >> i) & 1
        if sum == n :
                return i + 1
    return -1

Note: bit_length() is only in python 2.7 and 3

drankin2112 · Answer 4 · 2014-02-11T19:54:34.667

1

I don't speak python but this is how I would do it in c syntax. It should be easy to port over.

    int get2ndMSBIndex(int x) {

        x = x & (x - 1);   // Turn off rightmost 1-bit
        x = x & (-x);      // Isolate rightmost 1-bit. will be zero if none

        int pos = 0;

        while (x != 0) {
            x = x >> 1;
            pos++;
        }

        return pos;
    }

edited Feb 11 '14 at 19:54

answered Feb 11 '14 at 19:46

drankin2112

4,715
1
15
20

This assumes only 8-bit integers? – marshall Feb 11 '14 at 19:47
it applies to any size. just keeping it short for the example. you would need to expand case block, or write a loop. The point is that the bit is isolated. – drankin2112 Feb 11 '14 at 19:49
OK. Updated answer. Also, you don't have to check beforehand because it will return 0 if no bits. Good luck. Take care. – drankin2112 Feb 11 '14 at 19:57

Corley Brigman · Accepted Answer · 2014-02-11T19:20:38.303

0

Well, for gathering the nth set LSB, you might want to separate into getting rid of lower LSBs, and actually finding the index. To mask off a bit, you do need its value; you don't need to calculate its index. You can defer the index finding until the end. i.e.:

x = 0x188
# Find the value of the lowest bit, to clear.
least_power_of_2_x = ((x ^ (x-1)) + 1) >> 1
least_power_of_2_x
0x8

# Clear that bit
x = x ^ least_power_of_2_x
x
0x180

# Use same algorithm to find the next least
next_least = ((x ^ (x-1)) + 1) >> 1
next_least
0x80

# Now, you have the bit you actually care about. Find its index, 1-indexed.
next_least_index = len(bin(next_least)) - 2
next_least_index
8

edited Feb 11 '14 at 19:20

answered Feb 11 '14 at 16:40

Corley Brigman

11,633
5
33
40

I am not sure this works. x = 0x188 is the same as x = 392. bin(392) = '0b110001000'. Now least_power_of_2_x = 4. bin(x^4) = '0b110001100' which hasn't cleared the bit. Why are you doing it in hex out of interest? – marshall Feb 11 '14 at 16:51
maybe mixing algorithms? `392 ^ 391` == `15`, or `0xf`. `(15+1)<<2` == `8`, not `4`. ? Also, I use hex because when dealing with bitwise operations, hex or binary are easier for me to visualize than decimal, and hex numbers are shorter to type. – Corley Brigman Feb 11 '14 at 16:59
You have >> in your answer not <<. – marshall Feb 11 '14 at 17:07
you are right.. my fault, it was supposed to be `>> 1`, not `>> 2`. now it should be correct. – Corley Brigman Feb 11 '14 at 19:21

Index of second least significant set bit

5 Answers5