loremIpsum1771 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


One solution that wasn't mentioned was the python method:

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

Answer Source

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