BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 23 题

（二进制位加权和） 给定一个 $64$ 位二进制数 $x$，假设 $x$ 的二进制表示是 $a_{64}a_{63}\dots a_1$，即 $x=2^{63}a_{64}+2^{62}a_{63}+\dots+a_1$，求出 $ia_i$ 加起来的结果。

下面程序将使用倍增法解决该问题，我们以“求 $x$ 二进制表示下 $1$ 的个数”这一问题为例介绍倍增法的思想。

在一开始，我们把给定的 $x$ 看作是分成了 $64$ 块，每块长度为 $1$，每个块内的二进制数表示原数这个块内的 $1$ 的个数。

我们将进行若干轮操作，每轮合并两个相邻的块，让块长翻倍，合并成的新块上存的二进制数就是两个原块上存的二进制数加起来。

这个示例代码可以对 $0\sim 65535$ 的 $x$ 求出 $1$ 的个数：

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

typedef unsigned long long u64;
int main()
{
    u64 x;
    scanf("%llu", &x);
    x -= (x & 0xaaaaaaaaaaaaaaaaull) >> 1;
    x = (x & 0x3333333333333333ull) + ((x & 0xccccccccccccccccull) >> 2);
    x = (x & 0x0f0f0f0f0f0f0f0full) + ((x & 0xf0f0f0f0f0f0f0f0ull) >> 4);
    x = (x & 0x00ff00ff00ff00ffull) + ((x & 0xff00ff00ff00ff00ull) >> 8);
    printf("%llu\n", x);
    return 0;
}

请补全程序：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是用倍增思想算64位二进制位加权和，核心是‘先算区间和再合并’，从P= -1（全1掩码）开始，每轮取块长K，用R= P&Q截出当前块，把y里对应块的和加上移位后的块和，同时把x里对应块的和累加到y，循环6次正好覆盖64位，填空就是按这个逻辑找对应表达式。

最容易掉进‘掩码初始值’的坑：P若填0或1，第一轮R就全0，后面y永远不变，答案错成0或1；K若写成(1<<i)+1，当i=5时K=33，P/33无法整除导致块长不对齐，后面截取的R错位；移位量若用(1<<i)会越界，必须用i；y更新时若只加((y>>(1<<i))&R)会重复加高位块，必须用((y>>i)&Q)配合R再左移i，或者直接用((y>>(1<<i))&R)但前提是K对齐；x更新时若漏掉<<i，低位块和没挪到正确位置，导致最终y不是加权和而是普通位和。

【考点与概念】 这题考的是‘倍增（分治）位运算’：把64位拆成若干块，先算每块内1的个数，再把块合并成更大块，直到整段。关键掩码P= -1（二进制全1），右移i位后得到0..2^i-1全1，用来截出长度为2^i的块。 【命题视角】 命题人喜欢挖‘初始掩码’和‘块长公式’两个坑：若P填0或1，第一轮R全0，y永远不变；若K写成(1<<i)+1，i=5时K=33，P/33无法整除，块长错位。另外，y更新时若漏掉左移i，就把低位块和直接加到高位，答案错成普通位和。 【思考心法】 拿到题先想：要算加权和，必须把x里第j位乘j累加。倍增法先把x里每块的和算出来，存在y里，再把这些块的和按块长左移，累加到y。循环6次，块长从1,2,4,8,16,32，正好覆盖64位。 【逐空推演】 ① y初始应为0，因为还没算任何块和，所以填0（A）。 ② P初始应为全1掩码-1，这样才能保证第一轮R= -1&Q=Q，截出长度为1的块，所以填-1（C）。 ③ K是块长，每轮块长翻倍，第i轮（i从0到5）块长=2^i，但代码里P/=K，所以K应为2^{2^i}，即(1ull<<(1<<i))，且要+1得到长度为2^{2^i}的掩码，所以填(1ull<<(1<<i))+1（D）。 ④ y更新时，要把当前块和((y& R)）加上高位块和，高位块和是((y>>(1<<i))&R)，所以填((y>>(1<<i))&R)（A）。 ⑤ x更新时，要把低位块和((x& R)）加上高位块和左移i位，即(((x>>(1<<i))&R)<<i)，所以填(((x>>(1<<i))&R)<<i)（B）。 【避坑】

• P若填0或1，第一轮R全0，y永远不变，答案错成0或1。
• K若写成(1<<i)+1，i=5时K=33，P/33无法整除，块长错位，后面R截取的块不对齐。
• y更新时若只加((y>>(1<<i))&R)会重复加高位块，必须用((y>>(1<<i))&R)且前提是K对齐。
• x更新时若漏掉<<i，低位块和没挪到正确位置，导致最终y不是加权和而是普通位和。

【考频与趋势】 本题未标注关联知识点，但从近年CSP-J/S真题分布看，位运算与倍增思想属于高频考点，每年至少出现1-2次，常与进制转换、补码、异或性质结合命题。未来可能继续以‘补全程序’形式考查，也可能扩展到‘求某一位加权和’或‘动态更新块和’等变种。