current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite
1
 
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

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

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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();
share|improve this answer
1  
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 21 hours ago
    
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 15 hours ago
    
@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 15 hours ago
    
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 14 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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