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(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.
n has log(n) bits doesn't make the algorithm to count bits suddenly logarithmic.
count() method is going to be linear because the time to create and append to the string will dominate asymptotically? And also, wouldn't the algorithms in the article still be log(n) since there are log(n) bits?
bin(n).count('1') way... (about factor 1.3 slower for large strings, and about factor 2.6 slower for short strings, even when I prepare the table ahead of timing).'big' for endianness make any difference?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)).
O(log(n)) and it is also a O(m). When we say an algorithm is "linear", "quadratic" or "logarithmic" without precising the variable, the default one is the size of the input. Here it is m, not n. If this algorithm was said to be logarithmic, it would mean its complexity is a O(log(m)), i.e. a O(log(log(n))).n, and my algorithm has a O(log n) time complexity").
nis the total number of bits.count()function operates on any string and can't use those optimizations..count("1")has to visit each bit. Isbin(n)also linear?