统计fibonacci(1)到fibonacci(N)二进制表示中1的总个数

当然存在更高效的实现方案，朴素解法慢的核心原因是做了很多无用功，且复杂度随N增长过快：第N个斐波那契数的二进制长度约为0.69*N位，逐次计算、转字符串统计1的个数整体复杂度是O(N²)，N稍大就会出现明显卡顿。
可以根据需要处理的N的规模，选择不同层级的优化思路：

入门级优化：剔除冗余操作，打满线性效率 #

• 题目描述里的「把二进制字符串按顺序拼接」完全不需要实现：拼接后字符串里1的总个数，本质就是每个斐波那契数自身二进制中1的个数之和，真的去拼接字符串只会平白浪费内存和运行时间。
• 递推斐波那契数时不需要存储所有历史值，只用两个变量滚动保存前两项即可，空间复杂度可以压到最低。
• 不要手动转换二进制字符串统计1的个数，直接用编程语言内置的位计数接口：Python3.10及以上版本直接调用整数的.bit_count()方法，C++可以对大整数的每个存储块用__builtin_popcountll累加，效率比字符串统计高至少一个数量级。
  这种写法代码量极小，N在100万级别时基本几毫秒就能出结果，覆盖绝大多数日常使用场景，参考实现如下：

def calc_total_ones(n: int) -> int:
    if n < 1:
        return 0
    prev, curr = 0, 1  # 对应F(0)=0、F(1)=1的初始值
    total = 0
    for _ in range(n):
        total += curr.bit_count()
        prev, curr = curr, prev + curr
    return total

进阶级优化：分治快速倍增，适配超大N场景 #

如果需要处理的N达到1e8甚至更高量级，线性递推的效率还是不够，可以用斐波那契快速倍增的分治思路优化。
快速倍增的核心是利用斐波那契恒等式折半计算对应位置的数值，不需要逐次递推：

F(2k-1) = F(k)² + F(k-1)²
F(2k) = F(k) * (2*F(k-1) + F(k))
实现分治逻辑（递归/迭代均可）时，除了返回对应位置的斐波那契值，额外维护前k项斐波那契数的1的计数总和，合并子问题结果时直接累加，就能把时间复杂度从O(N)压缩到O(logN)级别（实际耗时主要来自大整数乘法，配合快速乘法算法，N到1e12级别都可以快速计算）。

几个需要避开的误区 #

• 不要白费力气寻找O(1)的通项公式：目前数论领域还没有发现斐波那契数二进制1的个数的通用简单规律，不存在一步算出结果的闭式公式。
• 不要为了提速用模运算截断斐波那契数：统计需要覆盖所有二进制位的1，截断高位会直接导致计数结果错误。
• 递推全程保持整数运算，不要做多余的类型转换，转字符串、转列表的操作都会大幅拉低运行效率。

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