I was asked the following question:
Given a number
num - write a function (in python) that counts the number of ones in its binary representation.
This is the answer i provided
def count_bits(num): res = 0 while num > 0: res += num & 1 num = num >> 1 return res
When asked about the complexity - i answered
n is the number of bits in the binary representation of
num. I was told there is another way to implement this to reduce runtime complexity. After a "hint" i have implemented it the following way
def count_bits(num): res = 0 while num > 0: res += 1 num = num & (num - 1) return res
but isn't this "at least not better" because of the subtraction operation?
from this wikipedia article on complexity of arithmetic operations the subtraction is
O(n) on 2 numbers with
Is there a difference in time complexity between the algorithms?
Which one is faster? (in theory and in practice)