Counting the number of bits of a positive integer

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<<a <= n:
        a <<= 1

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

10000 < 100000 < 101010 < 1000000 < 10000000 < 100000000

i.e. there is no relation between 1<<a and the number of bits in n. Choose a=1<<2, and 1<<a is too small. Choose a=1<<3 and 1<<a is too big. In the end, the only fact you know is that 1<<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>1:
        a >>= 1
        if n >= 1<<a:
            n >>= 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<<a in the sequence (since they vary so wildly, by 2**(2**n)).

    if n>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.

def bitcount(n):
    count = 0
    while n > 0:
        if (n & 1 == 1): count += 1
        n >>= 1

    return count

I didn’t read your code since, as mgibsonbr said, it’s unintelligible.

For an overview over more sophisticated ways to count bits, refer to the Bit Twittling Hacks page.

first of, I'm not really sure what your code does, at least not the first part. I'm also unsure if you wonder of the number of bits set, or the number of actual bits? The code under here does both:

#!/usr/bin/env python
import sys, math

def least_significant_bit_is_set (number):
    return (n & 1 == 1)

n = int (sys.argv[1])

#calculate number of set bits
bits_set = 0

while n > 0:
    if least_significant_bit_is_set (n):
      bits_set += 1
    n = n / 2

print bits_set

n = int (sys.argv[1])
# calculate total number of bits
bits = 0
if n > 0:
    bits = int (math.log (n,2)) + 1
print bits 

the n = n/2 could also be substituted by n >>= 1 to show that we are pushing the integer to the right, thereby loosing the least significant bit

If you consider readibility and maintainability as improvements and performance does not matter, you can rely on python string formatting to bit. That is convert the integer in a bit string, convert them back to integers and sum it.

sum(map(int,"{0:b}".format(n)))

Step by step interpretation:

>>> "{0:b}".format(1234)
'10011010010'
>>> map(int,_)
[1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0]
>>> sum(_)
5

Update:

"{0:b}".format() can be replaced by bin() built-in functions. Note that bin output is prefixed with "0b", so

sum(map(int,bin(n)[2:]))