Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Index of second least significant set bit

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).

like image 577
marshall Avatar asked Sep 18 '25 03:09

marshall


2 Answers

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()
like image 191
David Jones Avatar answered Sep 20 '25 19:09

David Jones


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) ) ) )
like image 27
lejlot Avatar answered Sep 20 '25 18:09

lejlot