CODEWITHSUNDEEP
pythonalgorithmbit-manipulation
loremIpsum1771
loremIpsum1771

Reputation: 2527

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?

Upvotes: 1

Views: 2636

Answers (2)

Martijn Pieters
Martijn Pieters

Reputation: 1124558

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(map(table.__getitem__, n.to_bytes(n.bit_length() // 8 + 1, 'little')))

However, because Python needs to produce a series of new objects (a bytes object and several integers) this method never quite is fast enough to beat the bin(n).count('1') method:

>>> from random import choice
>>> import timeit
>>> table = [0]
>>> while len(table) < 256:
...     table += [t + 1 for t in table]
...
>>> def perbyte(n): return sum(map(table.__getitem__, n.to_bytes(n.bit_length() // 8 + 1, 'little')))
...
>>> def strcount(n): return bin(n).count('1')
...
>>> n = int(''.join([choice('01') for _ in range(2 ** 16)]))
>>> for f in (strcount, perbyte):
...     print(f.__name__, timeit.timeit('f(n)', 'from __main__ import f, n', number=1000))
...
strcount 1.11822146497434
perbyte 1.4401431040023454

No matter the bit-length of the test number, perbyte is always a percentage slower.

Upvotes: 6

md5
md5

Reputation: 23727

Let's say you are trying to count the number of set bits of n. On Python typical implementations, bin will compute the binary representation in O(log n) time and count will go through the string, therefore resulting in an overall O(log n) complexity.

However, note that usually, the input parameter of algorithms is the "size" of the input. When you work with integers, this corresponds to their logarithm. That's why the current algorithm is said to have a linear complexity (the variable is m = log n, and the complexity O(m)).

Upvotes: 5

Related Questions