I think the running time of this should be \$O(log_{2}(n))\$:

def count_bits(num):
    assert num >= 0
    count = 0
    while (num != 0):
        num >>= 1
        count += 1
    return count

print count_bits(0) #0
print count_bits(2) #2
print count_bits(pow(10, 2)) #7
print count_bits(pow(10, 9)) #30

Your code is neat, variables are well named, the input validation is there, etc. It's all good. The assessment of your time complexity being \$O(\log_2{n})\$ is also right.

But, is that as good as it can be? Well, your time-complexity assessment is a hint as to what's a better solution... The base-2 log is also an indication of the number of bits used. Remember, in base 2, the number of bits needed increases at the exponential of 2 as well.

As a consequence, your function could be reduced to \$O(1)\$ with:

import math

def count_bitx(num):
    assert num >= 0
    if num == 0:
        return 0
    return 1 + int(math.log(num, 2))

Note that Python 3.1 introduced the bit_length() method, so you could do:

def count_bits(num):
    assert num >= 0
    return num.bit_length()
  • 1
    \$\begingroup\$ math.log is quite expensive though, so O's don't always tell you the whole truth. I guess using integer arithmetic should be faster than this code (though I might be wrong). \$\endgroup\$ – chaosflaws Sep 23 '15 at 15:34
  • \$\begingroup\$ It is the smallest number for which it happens, and it is pretty far out, but assert int(math.log(2**2955, 2)) == 2955 raises an AssertionError. \$\endgroup\$ – Jaime Sep 23 '15 at 21:33
  • \$\begingroup\$ @Jaime - Hmmm.... That's a big number. I guess that's why the fix for 3.1 using bit_length is in there ;-) I think if the OP's working in that scale of things, that a newer version of python would be warranted. Out of interest, did the performance remain O(1) or did the log process start slowing down when you got up there? \$\endgroup\$ – rolfl Sep 23 '15 at 21:38
  • \$\begingroup\$ The code I run was for j in range(3000): assert int(math.log(2**j, 2)) == j, and it completes in an eye blink, so speed doesn't seem to be a relevant concern. It is still flaky (and probably slower) to use floating point arithmetic for an integer operation. This seems to be the implementation of bit_length in Python 3.5, and here are several other possible approaches, and none of them uses anything other than integer arithmetic. \$\endgroup\$ – Jaime Sep 23 '15 at 21:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.