获取 1 位在 python Long 对象中的位置

Question

假设我在 python 2.7 中有一个非常非常大的 python 整数（尽管如果需要，我不介意切换到 python 3）。

比说的还要大，2^100000.

找到二进制序列中所有 1 的位置的最快方法是什么？ （例如：24 将是 11000 ---> = [4,5]（或 [5,4]。我不关心顺序）

目前我正在使用：

sum = whatever_starting_number

while 1:
    val = sum.bit_length()-1
    sum -= 2**val
    mylist.append(val)
    if sum == 0:
        break

这没问题，但它只比取 log2 并重复减去它快一点。其实我想做的就是看位，跳过零，记录1的位置，甚至不需要修改原始值。

edit：得到多个答案，真的很感激。我将在几次 timeit 测试中实施它们，明天将更新结果。

Answer 1

可能不是最快的解决方案，但相当简单并且看起来足够快（2 ^ 1M 是即时的）。

bits = []
for i, c in enumerate(bin(2**1000000)[:1:-1], 1):
    if c == '1':
        bits.append(i)

以防万一

[:1:-1]

不清楚，它被称为“扩展切片”，更多信息在这里：https://docs.python.org/2/whatsnew/2.3.html#extended-slices.

编辑：我决定对答案中发布的 3 个解决方案进行计时，结果如下：

import timeit


def fcn1():
    sum = 3**100000
    one_bit_indexes = []
    index = 0
    while sum: # returns true if sum is non-zero
        if sum & 1: # returns true if right-most bit is 1
            one_bit_indexes.append(index)
        sum >>= 1 # discard the right-most bit
        index += 1
    return one_bit_indexes


def fcn2():
    number = 3**100000
    bits = []
    for i, c in enumerate(bin(number)[:1:-1], 1):
        if c == '1':
            bits.append(i)
    return bits


def fcn3():
    sum = 3**100000
    return [i for i in range(sum.bit_length()) if sum & (1<<i)]


print(timeit.timeit(fcn1, number=1))
print(timeit.timeit(fcn2, number=1))
print(timeit.timeit(fcn3, number=1))

对于 3^100k：
fcn1: 0.7462488659657538
fcn2：0.02108444197801873
fcn3: 0.40482770901871845

对于 3^1M:
fcn1: 70.9139410170028
fcn2：0.20711017202120274
fcn3: 43.36111917096423

Answer 2

也许这足够快：

mylist = [i for i in range(sum.bit_length()) if sum & (1<<i)]

Answer 3

您可以使用按位运算符。

one_bit_indexes = []
index = 0
while sum: # returns true if sum is non-zero
    if sum & 1: # returns true if right-most bit is 1
        one_bit_indexes.append(index)
    sum >>= 1 # discard the right-most bit
    index += 1

还没有测试过这个，但很确定它会起作用。按位运算很快，所以这也应该比计算和减去 2 的幂更有效。（除非你的 Python 解释器已经在做一些聪明的事情，比如转换你的代码以用按位运算替换 2 的幂）。

edit：要使其适用于负数，您必须首先取“sum”的绝对值。

Answer 4

这个比

bin

方法快一倍：

lookup = [fcn2(i) for i in range(256)]

def fcn4(n):
    nbits = n.bit_length()
    nbytes = nbits//8 + 1
    unsigned_big = n.to_bytes(nbytes, "big", signed=False)
    return [i + rpos
            for i, b in zip(range(0, nbits, 8), unsigned_big)
            for rpos in lookup[b]]

如您所见，它使用另一种方法为所有字节生成查找表。

对于 3^100K：
fcn1：0.6382
fcn2：0.0116
fcn3：0.2926
fcn4：0.0052

对于 3^1M:
fcn1：62.4622
fcn2：0.1276
fcn3：31.8356
fcn4：0.0582