独热二进制序列中是否存在O(1)复杂度快速定位置位比特位置的方法

一、O(M) 复杂度的通用查找算法 #

你可以使用Brian Kernighan算法实现O(M)时间复杂度的查找，M为置位比特的总数量，核心原理是：执行num &= num - 1操作时，会直接清除当前num二进制表示中最低位的1，循环执行该操作直到num变为0，总循环次数等于置位比特总数，不需要遍历所有比特位。
对应Python实现如下：

def get_on_positions(num):
    res = []
    while num:
        # 提取当前最低位的1对应的独立数值
        lowest_set_bit = num & -num
        # 计算该位的索引位置
        pos = lowest_set_bit.bit_length() - 1
        res.append(pos)
        # 清除最低位的1，进入下一轮循环
        num &= num - 1
    return res

# 测试用例验证
assert get_on_positions(0b10010110) == [1,2,4,7]

二、独热编码场景下的O(1)定位方法 #

当输入确定为独热编码（即仅有一个置位比特，数值为2的整数次幂）时，完全可以实现O(1)复杂度的位置查询，不需要任何循环。
最简便的实现是直接调用Python内置的bit_length()方法，独热编码的二进制长度减1就是置位比特的索引：

def get_onehot_position(num):
    # 前提：num为非0的独热编码
    return num.bit_length() - 1

# 测试用例验证
assert get_onehot_position(0b10000000) == 7
assert get_onehot_position(0b100) == 2

如果需要增加输入合法性校验，避免非独热输入导致错误，可以加一行独热编码判断：

def get_onehot_position_safe(num):
    if num <= 0 or (num & (num - 1)) != 0:
        raise ValueError("输入不是合法的非0独热编码")
    return num.bit_length() - 1

该方法底层由C语言实现，直接读取整型数据的存储元信息，不需要遍历任何比特位，是真正的O(1)复杂度实现。

内容的提问来源于stack exchange，提问作者joseville