求 [l, r] 中二进制含奇数个 1 的数之和(l, r ≤ 10⁹)。
若一个正整数的二进制表示包含奇数个 1,则称它是有趣的。如 7 = (111)₂ 有 3 个 1 所以有趣;9 = (1001)₂ 有 2 个 1 所以不有趣。
给定 l、r,求所有满足 l ≤ n ≤ r 的有趣整数之和。
f(X) 为 [0, X] 中所有有趣数之和,答案 = f(r) − f(l−1)。f(X) 的关键是按二进制位"分块统计":从高位到低位,每当 X 的某一位是 1,就可以把"这一位取 0、低位任意"的数整体算一遍。二进制位统计前缀相减组合计数子块分解
| 项目 | 说明 |
|---|---|
| 输入 | 一行两个正整数 l、r |
| 输出 | 区间内有趣数之和 |
| 数据范围 | 1 ≤ l ≤ r ≤ 10⁹ |
| 有趣的定义 | 二进制表示中 1 的个数为奇数 |
| 注意 | r ≤ 10⁹ < 2³⁰,所以只需考虑 0 ~ 29 位 |
2^i 个数一定都 < X先直接列出区间内的数,确认理解正确。
| n | 二进制 | 1 的个数 | 有趣? |
|---|---|---|---|
| 3 | 11 | 2 | ✗ |
| 4 | 100 | 1 | ✓ |
| 5 | 101 | 2 | ✗ |
| 6 | 110 | 2 | ✗ |
| 7 | 111 | 3 | ✓ |
| 8 | 1000 | 1 | ✓ |
有趣的是 4、7、8 → 4 + 7 + 8 = 19 ✓
接下来用"前缀相减 + 按位分块"算一遍,验证方法的正确性。
0 = 0(0 个 1,偶)✗
1 = 1(1 个 1,奇)✓
2 = 10(1 个 1,奇)✓
f(2) = 1 + 2 = 3
f(2) = 3
按位分块计算(见下文的分块演示)
f(8) = 1 + 2 + 4 + 7 + 8 = 22
f(8) = 22
答案 = f(8) − f(2) = 22 − 3 = 19
✅ 19
8 = 1000₂,只有第 3 位是 1。
"高位与 X 相同、第 3 位取 0、低 3 位任意" 的数:
高位部分(第 4 位及以上)都是 0 → 前缀值 P = 0
这些数 = 0 ~ 7,共 8 个
前缀已确定的 popcount:pc = 0(偶数)
要让总的 popcount 为奇数 → 需要低 3 位的 popcount 为奇数
块 = [0, 7]
低 3 位中 popcount 为奇数的个数 = 2^(3−1) = 4
(分别是 001、010、100、111 → 1、2、4、7)
这 4 个数的和 = 1 + 2 + 4 + 7 = 14
贡献 14
扫完之后,还要单独看 X = 8 本身
popcount(8) = 1(奇数)→ 有趣
所以再加上 8
f(8) = 14 + 8 = 22 ✓
| 块(第 i 位) | 前缀 P | 前缀 pc | 需要的低位奇偶 | 个数 | 低位之和 |
|---|---|---|---|---|---|
| 第 3 位(取 0) | 0 | 0(偶) | 奇 | 2² = 4 | 2¹ × (2³−1) = 14 |
| X = 8 自身 | — | 1(奇) | — | 1 | 8 |
| 合计 | 5 | 22 |
i ≥ 1 时是 2^(i−1);而"低位值之和"的公式 2^(i−2) × (2^i − 1) 只在 i ≥ 2 时成立。i = 1 时:低位只有 0、1 两种,奇数 popcount 的只有 1,和为 1;偶数 popcount 的只有 0,和为 0。i = 0 时:低位为空,popcount 恒为 0(偶数),此时只有前缀 pc 为奇数才能凑成有趣。这两个特例是本题最容易写错的地方。f(r) 与 f(l−1) 各扫 30 位,用公式算每块贡献
f(r) − f(l−1) 把区间变成前缀;② 对 f(X) 从高位扫到低位,当 X 的第 i 位是 1 时,把"该位取 0、低位任意"的 2^i 个数用一个公式整体算掉。从 l 枚举到 r,用 __builtin_popcount 判断
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 按位分块 | O(30) | ✅ 稳过 |
| 逐数枚举 | O(r) = 10⁹ | ❌ 超时 |
输入 l 和 r,程序用"按位分块"算法计算结果,并与暴力枚举互相验证。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; // 求 [0, X] 中"二进制含奇数个 1"的所有数之和 long long f(long long X) { if (X < 0) return 0; long long res = 0; int pc = 0; // 已确定前缀中 1 的个数 for (int i = 30; i >= 0; i--) { if ((X >> i) & 1) { // 第 i 位为 1,可以"分块" long long cnt, sumLow; if (i >= 2) { cnt = 1LL << (i - 1); // 低位中奇数个 1 的个数 sumLow = (1LL << (i - 2)) * ((1LL << i) - 1); // 这些低位值之和 } else if (i == 1) { // 低位只有 0(偶)和 1(奇) if (pc % 2 == 0) { cnt = 1; sumLow = 1; } // 需要低位为奇 -> 取 1 else { cnt = 1; sumLow = 0; } // 需要低位为偶 -> 取 0 } else { // i == 0:低位为空,popcount 恒为 0(偶) if (pc % 2 == 1) { cnt = 1; sumLow = 0; } else { cnt = 0; sumLow = 0; } } long long pre = (X >> (i + 1)) << (i + 1); // 高位部分(i 位及以下清零) res += cnt * pre + sumLow; pc++; // 这一位沿 X 取 1,继续贴着走 } } if (pc % 2 == 1) res += X; // 别忘了 X 自身 return res; } int main() { long long l, r; scanf("%lld %lld", &l, &r); printf("%lld\n", f(r) - f(l - 1)); return 0; }
long long?因为答案可能达到 10¹⁷ 量级——例如 [1, 10⁹] 里有趣数的和约为总量的一半,约 2.5 × 10¹⁷,远超 int 上限。题目提示也专门说了这一点。另外 1LL << i 里的 LL 不能省,否则 1 << 30 虽然没溢出,但后续乘法会以 int 进行而溢出。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
for (i = 30; i >= 0; i--) | 位扫描 | r ≤ 10⁹ < 2³⁰,最高位是第 29 位 |
if ((X >> i) & 1) | 分块条件 | X 该位为 1 时才能"取 0 分块" |
cnt = 1LL << (i - 1) | 块内计数 | 低 i 位中奇偶 popcount 各占一半 |
sumLow = (1LL << (i-2)) * ((1LL << i) - 1) | 块内求和 | i ≥ 2 时的公式 |
if (pc % 2 == 1) res += X; | 补上 X | X 自身也要判断是否有趣 |
int(答案可达 10¹⁷);② 忘记最后的 res += X;③ i = 1 和 i = 0 忘了特判;④ 1 << i 没用 1LL 导致后续乘法溢出。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 8 | 19 | 题面样例 1:4 + 7 + 8 = 19 |
65 36248 | 328505490 | 题面样例 2 |
1 1 | 1 | 1 有趣 |
2 2 | 2 | 2 = 10₂ 有趣 |
1 7 | 14 | 有趣的是 1、2、4、7 → 1+2+4+7 = 14 |
1 1000000000 | 运行验证 | 最大范围,注意 long long |
i = 1(低位只有 0、1)与 i = 0(低位为空)不能套用 i ≥ 2 的公式。只用几个变量。
✅ 常数级运算,瞬间完成。这正是题目"时限下调"想要的解法——复杂度与数据规模无关。
// 数位统计的通用套路:把 [l, r] 化为 f(r) - f(l-1) // f(X):从高位到低位扫,遇到 X 的 1 位就"分块"统计 // 常见目标与对应做法 // 1. 统计个数 -> 块内计数(2^(i-1) 之类) // 2. 统计和 -> 块内计数 × 前缀值 + 低位之和 // 3. 统计平方和 -> 需要更复杂的展开(用 (P + l)^2) // 位运算相关的小工具 __builtin_popcount(x) // int 的 popcount __builtin_popcountll(x) // long long 的 popcount __builtin_parity(x) // popcount 的奇偶性(1 表示奇数) // 特例速记 // i >= 2:个数 2^(i-1),低位和 2^(i-2) * (2^i - 1) // i == 1:低位只有 0/1,奇数 popcount 的是 {1},和 = 1 // i == 0:低位为空(偶),只有 pc 为奇数时才算 1 个
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 前缀相减 | f(r) − f(l−1) | 所有"区间内满足条件的数"类问题 |
| 按位分块 | 遇到 1 位就整块统计 | 数位统计、数位 DP |
| 与数据规模无关的复杂度 | O(位数) | r 达 10⁹ ~ 10¹⁸ 的位统计题 |
cnt,去掉 sumLow 和 pre 的部分。这说明"计数"是"求和"的简化版,而求和的难点在于要额外维护"这些数的值"。)