CSES 1146题：统计1到n的置位总数，求优化方案

你的当前方案通过双重循环逐个数字统计置位，逻辑简单但时间复杂度为O(n*31)，当n取值很大时会超时，必须更换为按位计算的数学方法，直接统计每一位上1出现的总次数，时间复杂度可降至O(60)（对应64位整数的位数）。

优化思路：按位计算1的出现次数 #

对于二进制的第k位（从0开始计数，最低位为第0位），单独计算1到n中该位为1的数字总数，最后累加所有位的结果：

• 每2^(k+1)个数字为一个完整周期，每个周期内第k位会恰好出现2^k次1。
• 计算完整周期的数量：cycles = (n + 1) / (1 << (k + 1))，这部分贡献的1的数量为cycles * (1 << k)。
• 计算剩余未完成周期的数字中，第k位为1的数量：remainder = (n + 1) % (1 << (k + 1))，这部分的数量是max(0, remainder - (1 << k))。
• 将每一位的上述两部分结果相加，得到总置位次数。

优化后的代码 #

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long cnt = 0;
    for (int k = 0; k < 60; ++k) {
        long long cycle_len = 1LL << (k + 1);
        long long cycles = (n + 1) / cycle_len;
        cnt += cycles * (1LL << k);
        long long remainder = (n + 1) % cycle_len;
        cnt += max(0LL, remainder - (1LL << k));
    }
    cout << cnt << endl;
    return 0;
}

代码说明 #

• 改用long long类型，避免n较大时的整数溢出问题。
• 循环遍历每一位（覆盖到第60位，足够应对题目可能的n上限）。
• 按数学公式直接计算每一位的1出现次数，累加得到最终结果。

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