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
You are converting the integer to a string, which means it'll have to produce N
'1' characters. You then use
str.count() which must visit every character in the string to count the
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 =  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'))