a function to count the step reaching 0

Given a binary number, I need to write a function to count the total steps reaching zero. The rules are:

• If the number is even, divide it by 2
• If the number is odd, subtract 1 from it

for example, it takes six iterations for "1110" (14) to become 0:

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

I have come up with a naive solution that does calculations, but this algorithm cannot handle numbers that are very large.

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

what I need to know: How can I avoid doing the calculation and have an algorithm that is fast / can handle big numbers?

Assuming your code is correct and the rule is:

• test(0) = 0
• test(n) = 1 + test(n / 2) if n is even;
                1 + test(n − 1) otherwise

the important thing to notice is that:

• an even number ends with a binary 0
• dividing by 2 removes the 0 from the end (and nothing else)
• an odd number ends with a binary 1
• subtracting 1 turns the last 1 to a 0 (and nothing else)

So every 1 bit except for the first one adds 2 steps, and every significant 0 bit adds 1 step. That means for inputs that start with 1, you can write:

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

Now you just need to account for leading zeros, or just the specific case of "0" if leading zeros aren’t possible.