计算步数达到 0 的函数

Question

给定一个二进制数，我需要编写一个函数来计算达到零的总步数。规则是：

• 如果数字是偶数，则除以 2
• 如果数字是奇数，则减去 1

例如，“1110”(14) 需要迭代 6 次才能变为 0：

• 14 / 2 = 7
• 7 - 1 = 6
• 6 / 2 = 3
• 3 - 1 = 2
• 2 / 2 = 1
• 1 - 1 = 0

我提出了一个简单的解决方案来进行计算，但该算法无法处理非常大的数字。

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

test("1000")
Out[65]: 4

test("101")
Out[66]: 4

test("001")
Out[67]: 1

test("0010010001")
Out[68]: 10

test("001001")
Out[69]: 5

我需要知道什么：如何避免进行计算并拥有快速/可以处理大数字的算法？

Answer 1

假设您的代码是正确的并且规则是：

\n\n

\n
• 测试(0) = 0
\n
• test(n) = 1 + test(n / 2) 如果 n 是偶数；
  \n\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0 \xc2\xa0\xc2\xa01 + test(n − 1) 否则
\n

\n\n

需要注意的重要一点是：

\n\n

\n
• 偶数以二进制 0 结尾
\n
• 除以 2 会删除末尾的 0（没有其他内容）
\n
• 以二进制 1 结尾的奇数
\n
• 减去 1 将最后一个 1 变为 0（没有其他值）
\n

\n\n

因此，除了第一个位之外，每一位都增加 2 个步长，并且每个有效的 0 位都增加 1 个步长。这意味着对于以1，您可以编写：

\n\n

def test(x):\n    return x.count(\'1\') + len(x) - 1\n

\n\n

现在您只需要考虑前导零，或者只考虑特定情况"0"前导零是否可能\xe2\x80\x99t 的特定情况。

\n