CODEWITHSUNDEEP
pythonalgorithm
user8391780
user8391780

Reputation:

Python: How to efficiently count the number of "1"s in the binary representation of 1 to n numbers?

E.g. For the input 5, the output should be 7. (bin(1) = 1, bin(2) = 10 ... bin(5) = 101) --> 1 + 1 + 2 + 1 + 2 = 7

Here's what I've tried, but it isn't a very efficient algorithm, considering that I iterate the loop once for each integer. My code (Python 3):

i = int(input())
a = 0
for b in range(i+1):
  a = a + bin(b).count("1")
print(a)

Thank you!

Upvotes: 1

Views: 476

Answers (2)

Bill Bell
Bill Bell

Reputation: 21643

gmpy2, due to Alex Martella et al, seems to perform better, at least on my Win10 machine.

from time import time
import gmpy2

def onecount(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        m = n/2
        return onecount(m) + onecount(m-1) + m
    m = (n-1)/2
    return 2*onecount(m)+m+1

N = 10000

initial = time()
for _ in range(N):
    for i in range(30):
        onecount(i)
print (time()-initial)

initial = time()
for _ in range(N):
    total = 0
    for i in range(30):
        total+=gmpy2.popcount(i)
print (time()-initial)

Here's the output:

1.7816979885101318
0.07404899597167969

If you want a list, and you're using >Py3.2:

>>> from itertools import accumulate
>>> result = list(accumulate([gmpy2.popcount(_) for _ in range(30)]))
>>> result
[0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71]

Upvotes: 1

Spacedman
Spacedman

Reputation: 94192

Here's a solution based on the recurrence relation from OEIS:

def onecount(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        m = n/2
        return onecount(m) + onecount(m-1) + m
    m = (n-1)/2
    return 2*onecount(m)+m+1

>>> [onecount(i) for i in range(30)]
[0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71]

Upvotes: 5

Related Questions