loremIpsum1771 - 1 year ago 70

Python Question

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()`

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?

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'))
```