python - Python:如何有效地计算1到n个数字的二进制表示形式中“1”的数量？

例如，对于输入5，输出应为7。
（仓（1）=1，仓（2）=10料仓（5）=101）-->1+1+2+1+2=7
这是我尝试过的，但它不是一个非常有效的算法，因为我为每个整数迭代一次循环我的代码（Python3）：

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

谢谢您！

最佳答案

以下是基于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]

关于python - Python:如何有效地计算1到n个数字的二进制表示形式中“1”的数量？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47730349/