如何快速获取Python超大整数二进制中1的位位置？

嘿，这个问题问到点子上了！处理远超2^100000的超大整数，效率确实是核心痛点。先聊聊你当前的方法——思路是对的，但每次计算2**val再做减法，对于超大整数来说其实挺耗性能的：生成2**val这个巨数本身就需要开销，减法操作也要反复处理两个超大整数，整体效率不算最优。

下面给你几个更快的方案，都是基于位运算（底层优化过，速度拉满），而且在Python2.7和Python3都能跑：

方案1：从低位到高位遍历（最通用，兼容性拉满） #

这个方法直接逐位检查每一位是否为1，用位运算替代复杂的整数运算，每一步都是轻量级操作：

def get_1_positions_1based(n):
    positions = []
    idx = 1  # 对应1-based的位置，和你的示例一致
    while n:
        if n & 1:  # 检查当前最低位是否为1
            positions.append(idx)
        n >>= 1  # 右移一位，相当于除以2
        idx += 1
    return positions

比如传入24，会返回[4,5]，完全匹配你的示例。如果想要0-based的位置，把idx初始化为0就行。

方案2：只循环1的个数（效率更高，适合1较少的情况） #

如果整数中1的数量远小于二进制位数，这个方法更快——每次清除最右边的1，循环次数等于1的个数：

def get_1_positions_high_first(n):
    positions = []
    while n:
        bit_len = n.bit_length()
        pos = bit_len  # 1-based的高位位置
        positions.append(pos)
        # 直接清除当前最高位的1，比减法高效
        n &= ~(1 << (bit_len - 1))
    return positions

传入24会返回[5,4]，顺序是从高位到低位，和你的示例顺序相反但结果正确。如果想要从低位到高位，也可以用n &= n-1配合计数：

def get_1_positions_low_first(n):
    positions = []
    idx = 1
    while n:
        if n & 1:
            positions.append(idx)
        n &= n - 1  # 清除最右边的1
        idx += 1
    return positions

对你原方法的优化 #

如果你不想大改代码，把2**val换成1 << val就能提升不少速度——位运算生成的整数比幂运算高效得多，再把减法换成位清除操作会更快：

sum = whatever_starting_number
mylist = []
while sum:
    val = sum.bit_length() - 1
    mylist.append(val + 1)  # 转成1-based位置
    sum &= ~(1 << val)  # 替代减法，直接清除该位的1
    if sum == 0:
        break

版本兼容说明 #

这些方法在Python2.7和Python3都能正常运行，不需要强制切换版本。不过Python3的整数底层实现更高效，处理极端大的整数时会比Python2.7快一些。

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