python之根据 python 中的给定条件最小化 n 的最快方法

我怎样才能使下面的代码更快？输入是二进制字符串，我正在将其转换为数字。可能我需要使用二进制字符串而不是数字？该算法只能从输入中除以 2 或减去 1。我尝试了下面的代码，但速度不够快。

我尝试了以下:

def steps_to_zero(n) :  
 
    n=int(n,2) 
    count = 0 
    while n > 0: 
        if n % 2 == 0:             
            n = n // 2 
        else:   
            n = n - 1 
 
        count += 1 
    return (count) 

它必须比这个快两倍:

def steps_to_zero_v1(x): 
    x_int = int(x,2) 
    steps = 0 
    while x_int != 0: 
        if x_int % 2 == 0: 
            x_int = x_int // 2  
        else: 
            x_int = x_int - 1 
        steps += 1 
    return steps 
 

请您参考如下方法:

您建议的代码与给定的代码完全相同。 您想要加快速度的主要事情是摆脱昂贵的 if n % 2 == 0 测试。

解决方案是您可以在位级别上推理这个问题，而无需进行任何强力计算。

对于简单的情况n=0，我们得到count=0。对于下一个更简单的情况 n=1，我们只需减去 1 一次，得到 count=1。

在所有其他情况下，我们正在处理一些更长的二进制数。如果该数字的最后一位是 0，我们可以除以 2 使我们的二进制数字更短:

...x0 / 2 = ...x  # 1 step for 1 digit shorter 

否则我们必须先减 1 才能除以二。

...x1 - 1 = ...x0 
...x0 / 2 = ...x   # 2 steps for 1 digit shorter 

换句话说:对于最左边的 1，我们需要 1 次操作，对于所有数字，如果是 0 则需要 1，如果是 1 则需要 2。

这意味着您可以简单地通过计算字符串中 1 的数量来计算:

def steps_to_zero(n): 
    n = n.lstrip('0')            # remove leading zeroes if they occur 
    divisions = len(n) - 1       # don't have to divide for the left-most 1 
    subtractions = n.count('1')  # each 1 needs a subtraction to become a 0 
    return divisions + subtractions 

% 2 和 .count('1') 平均超过 0-10,000 的时间比较:

# % 2 
$ python3 -m timeit -s "x=list(range(10000))" "[y%2 for y in x]" 
1000 loops, best of 3: 277 usec per loop 
 
# .count('1') 
$ python3 -m timeit -s "x=[bin(i) for i in range(10000)]" "[y.count('1') for y in x]" 
1000 loops, best of 3: 1.35 msec per loop 

尽管每次执行 .count('1') 比 %2 慢 ~5 倍，.count('1')只需执行一次，而 %2 必须执行 log2(n) 次。这使得 .count('1') 方法在 n > 2**5 (=32) 时更快。