loremIpsum1771 - 1 year ago 148
Python Question

# Counting the number of set bits in a number

The problem statement is:

Write an efficient program to count number of 1s in binary representation of an integer.

I found a post on this problem here which outlines multiple solutions which run in log(n) time including Brian Kernigan's algorithm and the gcc

`__builtin_popcount()`
method.

One solution that wasn't mentioned was the python method:
`bin(n).count("1")`

which also achieves the same effect. Does this method also run in log n time?

You are converting the integer to a string, which means it'll have to produce N `'0'` and `'1'` characters. You then use `str.count()` which must visit every character in the string to count the `'1'` characters.

All in all you have a O(N) algorithm, with a relatively high constant cost.

Note that this is the same complexity as the code you linked to; the integer `n` has log(n) bits, but the algorithm still has to make N = log(n) steps to calculate the number of bits. The `bin(n).count('1')` algorithm is thus equivalent, but slow as there is a high cost to produce the string in the first place.

At the cost of a table, you could move to processing integers per byte:

``````table = [0]
while len(table) < 256:
table += [t + 1 for t in table]

length = sum(table[b] for b in n.to_bytes(n.bit_length() // 8 + 1, 'little'))
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download