[Python] 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?

Continue reading...