大数值场景下二进制1的个数总和统计的内存优化与性能提升方案咨询

嘿，你的问题很典型——当处理像562949953421310这样的超大数值时，用列表存储0到该数的所有元素再逐个修改，必然会因为内存占用过高报错。毕竟这个列表要包含500多万亿个元素，哪怕每个元素只占4字节，内存需求也会达到2PB以上，这显然不现实。咱们来一步步优化：

第一步：去掉冗余列表，直接累加（基础内存优化） #

原来的代码里，列表y完全是多余的——你不需要存储所有数的1的个数，只需要一个累加变量来统计总和就行。这样内存占用会降到O(1)（只用到几个变量），虽然时间复杂度还是O(n)，但至少不会爆内存了：

a = int(input())
total = 0
for i in range(a + 1):
    total += bin(i).count('1')  # bin()比format()更直接生成二进制字符串
print(total)

不过要注意，对于5e14这样的超大数，这个循环还是要执行500多万亿次，速度会非常慢。所以咱们需要更高效的数学方法。

第二步：按二进制位统计（O(log n)时间复杂度，终极优化） #

核心思路是逐位计算每个二进制位上1出现的总次数，然后把所有位的结果相加。因为二进制每一位的1出现规律是周期性的：

• 对于第k位（从0开始，最低位为第0位），每2^(k+1)个数为一个周期
• 每个周期内，该位会恰好出现2^k次1
• 最后计算完整周期的贡献，再加上剩余部分中该位出现的次数

具体实现代码 #

def count_total_ones(n):
    total = 0
    k = 0
    # 遍历每一个二进制位，直到该位的权值超过n
    while (1 << k) <= n:
        cycle_length = 1 << (k + 1)  # 2^(k+1)，周期长度
        full_cycles = (n + 1) // cycle_length  # 完整周期的数量
        # 每个完整周期贡献2^k个1
        total += full_cycles * (1 << k)
        # 计算剩余数字中该位为1的数量
        remainder = (n + 1) % cycle_length
        total += max(0, remainder - (1 << k))
        k += 1
    return total

a = int(input())
print(count_total_ones(a))

原理示例（以n=5为例） #

n=5的二进制是101，咱们逐位计算：

• 第0位（权值1）：周期长度2，完整周期数=(5+1)//2=3，贡献3*1=3；余数0，额外贡献0 → 总计3次
• 第1位（权值2）：周期长度4，完整周期数=(5+1)//4=1，贡献1*2=2；余数2，2-2=0 → 总计2次
• 第2位（权值4）：周期长度8，完整周期数=0，贡献0；余数6，6-4=2 → 总计2次
• 总和：3+2+2=7，和实际统计0-5的1的个数总和（0+1+1+2+1+2=7）完全一致

这个方法的循环次数只和n的二进制位数有关，比如5e14的二进制只有49位，循环49次就能出结果，速度快到可以忽略不计，内存也只用到几个变量。

对比三种方案 #

内容的提问来源于stack exchange，提问作者1bitPython