题解

题面描述

给定正整数 $n$，定义对每个整数 $x$ 的“退化运算”：

1. 计算

   $$Back_x = x\;\text{and}\;(-x)$$

   其中 and 表示按位与运算。

2. 若 $Back_x>0$，则令

   • 新的 $x \leftarrow x - Back_x$；

   • 本次退化的消耗为

     $$\max(0, Back_x - 1).$$

3. 重复上述步骤，直到 $x=0$ 为止。

我们记数字 $x$ 在整个退化过程中的 总消耗 $Cost_x$ 为：

• 初始的 $x$ 与每次退化的消耗值，全部按位或得到的结果。

即

现在要求计算

思路

1. 观察 $Cost_x$ 的结构：

   • 退化过程中，每一步的 $Back_x$ 恰好是 $x$ 的最低位的 1 所对应的 $2^k$。

   • 相应的消耗 $\max(0,Back_x-1)=2^k-1$（当 $k=0$ 时为 0）。

   • 将所有这些消耗值按位或，再与初始的 $x$ 按位或，最终得到：

     

   • 注意到如果 $x$ 的最高位在位置 $k$，那么 $x$ 的二进制第 $k$ 位为 1，而所有 $2^j-1$ ($j\le k$) 的按位或，会使得最终结果的二进制位 $0,1,\dots,k$ 全部为 1，即：

     $Cost_x$ = $2^{k+1}-1$,$k$ = $\lfloor\log_2 x\rfloor.$

2. 转化为求和：

3. 高效计算：

   • 对每个 $k=0,1,2,\dots,\lfloor\log_2 n\rfloor$，令区间

     $L_k$ = $2^k$,$R_k$ =min($n$,$2^{k+1}-1$).

   • 在此区间内，$\lfloor\log_2 i\rfloor = k$ 的 $i$ 有

     $cnt_k$ = $R_k$ - $L_k$ + $1$

   • 因此

     

   • 最终答案为

     

C++

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;  // 读取测试用例个数
    while (T--) {
        int64 n;
        cin >> n;  // 对每个测试读取 n

        int64 sum_pow = 0;
        // 枚举 k 表示 2^k
        for (int k = 0; (1LL << k) <= n; ++k) {
            int64 L = 1LL << k;
            int64 R = min(n, (1LL << (k + 1)) - 1);
            int64 cnt = R - L + 1;  // 区间内 i 的个数
            sum_pow += cnt * L;     // 累加 cnt * 2^k
        }

        // 最终结果为 2 * sum_pow - n
        int64 ans = 2 * sum_pow - n;
        cout << ans;
        if (T) cout << ' ';
    }
    return 0;
}

Python

import sys

# 处理输入
input = sys.stdin.readline
T = int(input())  # 读取测试用例数
for _ in range(T):
    n = int(input())  # 读取 n

    sum_pow = 0
    k = 0
    # 枚举各个二进制位
    while (1 << k) <= n:
        L = 1 << k
        R = min(n, (1 << (k + 1)) - 1)
        cnt = R - L + 1  # 区间 [2^k, 2^(k+1)-1] 内的数目
        sum_pow += cnt * L
        k += 1

    # 按公式计算
    ans = 2 * sum_pow - n
    print(ans, end=' ')

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();  // 读取测试用例数量

        while (T-- > 0) {
            long n = sc.nextLong();  // 读取 n

            long sumPow = 0;
            // 枚举 k，使 2^k <= n
            for (int k = 0; (1L << k) <= n; k++) {
                long L = 1L << k;
                long R = Math.min(n, (1L << (k + 1)) - 1);
                long cnt = R - L + 1;  // 区间长度
                sumPow += cnt * L;     // 累加 cnt * 2^k
            }

            // 计算最终答案
            long ans = 2 * sumPow - n;
            System.out.print(ans);
            if (T > 0) System.out.print(" ");
        }

        sc.close();
    }
}

题目内容

小美有一些运算：她定义一个整数 $x$ 的退化运算 $Back_x$ 为自己按位与自己的负数，形式化的说， $Back_x=(x)and(-x)$ ；一次成功的退化后，$x$ 变为 $x-Back_x$ ；消耗为 $max$ { $0,Back_x-1$ } 。

退化是可以持续的进行的，例如，当 $x=37$ 时：

• 第一次退化，$x=37$，$Back_{37}=(37)and(-37)=1$，退化为 $37-Back_{37}=36$ ，消耗 $0$ ；

• 在刚刚的基础上进行第二次退化，$x=36,Back_{36}=(36)and(-36)=4$，退化为 $36-Back_{36}=32$ ，消耗 $3$ ；

• 在刚刚的基础上进行第三次退化，$x=32$ , ......

• ......

我们记数字 $x$ 退化过程中的总消耗 $Cost_x$ 为：初始的 $x$ 与每一次退化的消耗 按位或 后得到的结果。

例如 $Cost_{37}=37$ $or$ $0$ $or$ $3$ $or$ $···$ 。

现在，你已经完全掌握小美的运算了，你需要计算的是，$1$ ~ $n$ 中，全部数字退化总消耗之和，即

$\sum_{i=1}^{n}Cost_i$ 。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≦T≦2×10^5)$ 代表数据组数，每组测试数据描述如下：

在一行上输入一个整数 $n(1 ≦n≦ 10^9)$ 代表运算的上界。

输出描述

对于每一组测试数据，在同一行上连续输出一个整数，代表 $1$ ~ $n$ 中，全部数字退化总消耗之和。

样例1

输入

5
1
2
3
4
11451

输出

1 4 7 14 981396131

说明

$Cost_1=1,Cost_2=3,Cost_3=3,Cost_4=7$ 。