第3题

using i64 = long long;

i64 solve1(i64 n)
{
    std::vector<i64> c(n);
    c[0] = 0;
    i64 sum = 0;
    for (i64 i = 1; i < n; ++i)
    {
        c[i] = c[i / 2] + (i % 2);
        sum += c[i];
    }
    return sum;
}

std::pair<i64,i64> solve2(i64 n)
{
    if (n == 0)
        return {0, 0};
    auto r = n % 2;
    auto q = n / 2;
    auto [s, c] = solve2(q);
    if (r == 1)
        return {s*2 + q + c, c + 1};
    else
        return {s*2 + q, c};
}

solve1(n) 计算的是（ ）。

{{ select(1) }}

• 0到 $n-1$ 之间，全体二进制数的零出现的数量
• 0到 $n-1$ 之间，全体二进制数的一出现的数量
• 0到 $n$ 之间，全体二进制数的零出现的数量
• 0到 $n$ 之间，全体二进制数的一出现的数量