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 O(n) where 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 n bits. Is there a difference in time complexity between the algorithms? Which one is faster? (in theory and in practice)

  • $\begingroup$ Also the & operator will need $O(n)$ time. $\endgroup$
    – nir shahar
    Jan 14 at 21:41
  • 1
    $\begingroup$ It depends on your model of computation, and on whether the input is “large” or not. In the RAM model, arithmetic on machine words takes constant time. $\endgroup$ Jan 14 at 22:47
  • $\begingroup$ Which one is faster in practice? Try them out! $\endgroup$ Jan 15 at 16:41
  • $\begingroup$ @YuvalFilmus - already did and it depends. for numbers with a lot of 0s in their binary representation (2^i where 0<i<10000) - the second approach is faster and for numbers with a lot of 1s in their binary representation (2^i-1 where 0<i<10000) it seems that the first approach performs better. $\endgroup$
    – Mr T.
    Jan 17 at 16:01
  • $\begingroup$ Now you need to decide whether you are interested in worst case complexity, average case complexity, or something else. If you are interested in average case complexity, you need to decide on a distribution with respect to which you take the average. Then you can repeat the experiments, with your chosen form of time complexity in mind. (If you chose worst-case and the numbers are very large, you might need to figure out first what inputs are the worst.) $\endgroup$ Jan 17 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.