Given a binary number/sequence, find the positions/bit indices of the 1/ON/SET/HIGH bits. As an example, given the binary number:
76543210 # positions
0b10010110 # binary number
^ ^ ^^
the positions would be [1,2,4,7].
I have the following O(N) algorithm (where N is the bit length of the binary number):
def get_on_positions(num):
res = []
pos = 0
while num:
if num & 0b1:
res.append(pos)
num >>= 1
pos += 1
return res
assert(get_on_positions(0b10010110) == [1,2,4,7])
But I was wondering: is there was a faster O(M) algorithm (where M is the count of ON/SET/HIGH bits in the binary number). A particular case where the difference between N (the bit length) and M (the count of ON/SET/HIGH bits) can be significant is when the binary number is one-hot. A one-hot binary number has exactly one of its bits ON/SET/HIGH). For example 0b10000000 (or any power of 2). In the one-hot case, is there an O(1) algorithm for finding the position of the single ON/SET/HIGH bit? As a side note, the case where num is one-hot case is equivalent to finding log_2(num).
