Counting the number of bits of a positive integer How can I improve this code for counting the number of bits of a positive integer n in Python?

def bitcount(n):
    a = 1
    while 1&lt;&lt;a &lt;= n:
        a &lt;&lt;= 1

    s = 0
    while a&gt;1:
        a &gt;&gt;= 1
        if n &gt;= 1&lt;&lt;a:
            n &gt;&gt;= a
            s += a
    if n&gt;0:
        s += 1

    return s
The very first thing you should do to improve it is comment it. I'm reading it for almost half an hour and still can't understand what it does. I tested it, and it indeed work as intended, but I have no idea why. What algorithm are you using?

I pointed below parts of the code that aren't clear to me. Since @blufox already presented a simpler way to count bits (that works for non-zero numbers), I won't bother to suggest an improvement myself.

def bitcount(n):
    a = 1
    while 1&lt;&lt;a &lt;= n:
        a &lt;&lt;= 1


Why is a growing in powers of two, while you're comparing 1&lt;&lt;a to n? The sequence you're generating in binary is 10 100 10000 100000000 10000000000000000 ... Take n=101010, and notice that

10000 &lt; 100000 &lt; 101010 &lt; 1000000 &lt; 10000000 &lt; 100000000

i.e. there is no relation between 1&lt;&lt;a and the number of bits in n. Choose a=1&lt;&lt;2, and 1&lt;&lt;a is too small. Choose a=1&lt;&lt;3 and 1&lt;&lt;a is too big. In the end, the only fact you know is that 1&lt;&lt;a is a power of two smaller than n, but I fail to see how this fact is relevant to the task.

    s = 0
    while a&gt;1:
        a &gt;&gt;= 1
        if n &gt;= 1&lt;&lt;a:
            n &gt;&gt;= a
            s += a


This removes a bits from n, while increasing the bit count by a. That is correct, but I fail to understand why the resulting n will still have fewer bits than the next 1&lt;&lt;a in the sequence (since they vary so wildly, by 2**(2**n)).

    if n&gt;0:
        s += 1

    return s


I see that the result is off by 1 bit, and your code correctly adjust for that. Again, no idea why it does that.