# Counting the number of bits of a positive integer #2

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()

• 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). – chaosflaws Sep 23 '15 at 15:34
• 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. – Jaime Sep 23 '15 at 21:33
• @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? – rolfl Sep 23 '15 at 21:38
• 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. – Jaime Sep 23 '15 at 21:52