GESP 题解库 / 5 级题解 / [GESP202509 五级] 有趣的数字和 · 第 5 / 23 题
GESP202509 五级 · P14074 · 中等

有趣的数字和

求 [l, r] 中二进制含奇数个 1 的数之和(l, r ≤ 10⁹)。

📊
l, r ≤ 10⁹
数据范围
🔢
long long
数值类型
⚡
O(30)
时间复杂度
🎯
按位统计 + 前缀相减
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

若一个正整数的二进制表示包含奇数个 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 位

需要解决的问题

02
思维导图
整理解题思路的全貌
🔟 按位分块 + 前缀相减
🧮 前缀相减
记 f(X) = [0,X] 中有趣数之和
答案 = f(r) − f(l−1)
把区间问题化为前缀问题
f 只需处理单点
📦 分块思想
从高位到低位扫 X
X 的某位为 1 时
"该位取 0、低位任意"整块 < X
每块大小 2^i
📐 块内公式
前缀 popcount 记为 pc
需要 pc + 低位 popcount 为奇
低位 i 位中奇/偶各 2^(i−1) 个
块的和也有闭式公式
⚠️ 易错点
答案超 int(Σn 可达 10¹⁷)
忘加 X 自身
i = 0 与 i = 1 需特判
低位和的公式记错
03
样例手算推导
样例 [3, 8] 的逐步统计

🧮 样例 1:l = 3,r = 8,答案 19

先直接列出区间内的数,确认理解正确。

n二进制1 的个数有趣?
3112✗
41001✓
51012✗
61102✗
71113✓
810001✓

有趣的是 4、7、8 → 4 + 7 + 8 = 19 ✓

接下来用"前缀相减 + 按位分块"算一遍,验证方法的正确性。

1
先算 f(2):[0, 2] 中的有趣数

0 = 0(0 个 1,偶)✗

1 = 1(1 个 1,奇)✓

2 = 10(1 个 1,奇)✓

f(2) = 1 + 2 = 3

f(2) = 3

2
再算 f(8)

按位分块计算(见下文的分块演示)

f(8) = 1 + 2 + 4 + 7 + 8 = 22

f(8) = 22

3
相减

答案 = f(8) − f(2) = 22 − 3 = 19

✅ 19

📌
注意 f(2) 包含 2 而 f(8) − f(2) 不含——[0,8] 减去 [0,2] 正好是 [3,8],所以 2 被正确排除。这就是"前缀相减"必须用 f(r) − f(l−1) 的原因。

🧮 f(X) 的按位分块演示(X = 8)

8 = 1000₂,只有第 3 位是 1。

1
扫到第 3 位(X 此位为 1)

"高位与 X 相同、第 3 位取 0、低 3 位任意" 的数:

高位部分(第 4 位及以上)都是 0 → 前缀值 P = 0

这些数 = 0 ~ 7,共 8 个

前缀已确定的 popcount:pc = 0(偶数)

要让总的 popcount 为奇数 → 需要低 3 位的 popcount 为奇数

块 = [0, 7]

2
算这一块的个数与和

低 3 位中 popcount 为奇数的个数 = 2^(3−1) = 4

(分别是 001、010、100、111 → 1、2、4、7)

这 4 个数的和 = 1 + 2 + 4 + 7 = 14

贡献 14

3
别忘了 X 自己

扫完之后,还要单独看 X = 8 本身

popcount(8) = 1(奇数)→ 有趣

所以再加上 8

f(8) = 14 + 8 = 22 ✓

块(第 i 位)前缀 P前缀 pc需要的低位奇偶个数低位之和
第 3 位(取 0)00(偶)奇2² = 42¹ × (2³−1) = 14
X = 8 自身—1(奇)—18
合计522
⚠️
公式的两个特例:低 i 位中"popcount 为奇"的个数,在 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 为奇数才能凑成有趣。这两个特例是本题最容易写错的地方。
04
解法对比
按位分块 vs 逐数枚举

⚔️ 解法对比

🟢 按位分块统计(推荐) 推荐

f(r) 与 f(l−1) 各扫 30 位,用公式算每块贡献

  • 时间 O(30)
  • 常数极小,瞬间完成
  • 代码 30 行
  • 空间 O(1)
💡
核心两步:① 用 f(r) − f(l−1) 把区间变成前缀;② 对 f(X) 从高位扫到低位,当 X 的第 i 位是 1 时,把"该位取 0、低位任意"的 2^i 个数用一个公式整体算掉。

🟠 逐数枚举 + popcount

从 l 枚举到 r,用 __builtin_popcount 判断

  • 时间 O(r) = 10⁹
  • 题目已提示"时限下调"
  • 必然超时
  • 只能通过 40% 的小数据
⚠️
注意题目的提示:"为保证只有时间复杂度合理的算法通过本题,本题时限下调"——这等于明示"O(r) 的暴力过不了"。看到 r ≤ 10⁹ 且要统计"位"相关性质,就该想到"按位分块 / 数位 DP"。

📈 性能对比

方案复杂度可行性
按位分块O(30)✅ 稳过
逐数枚举O(r) = 10⁹❌ 超时
05
算法流程图
前缀相减 + 按位分块统计
开始读入 l、r;答案 = f(r) − f(l − 1)进入 f(X):res = 0,pc = 0(前缀的 popcount)i 从 30 递减到 0X 的第 i 位是否为 1?是 ✓计算这一块否 ✗i 减 1按公式算出"该位取 0"那一块的个数与和,累加进 respc 加 1(这一位沿 X 取 1,继续贴着走)扫描结束后 pc 是否为奇数?是 ✓res 再加上 X 自身(因为 X 也有趣)否 ✗不加返回 resi 减 1 处理低位
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔟 有趣的数字和

输入 l 和 r,程序用"按位分块"算法计算结果,并与暴力枚举互相验证。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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;补上 XX 自身也要判断是否有趣
⚠️
四个坑:① 用 int(答案可达 10¹⁷);② 忘记最后的 res += X;③ i = 1 和 i = 0 忘了特判;④ 1 << i 没用 1LL 导致后续乘法溢出。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 819题面样例 1:4 + 7 + 8 = 19
65 36248328505490题面样例 2
1 111 有趣
2 222 = 10₂ 有趣
1 714有趣的是 1、2、4、7 → 1+2+4+7 = 14
1 1000000000运行验证最大范围,注意 long long
✅
自查清单:① 用 long long 吗?② 加上了 X 自身吗?③ 两个特判写了吗?

🚨 易错点清单

⚠️
用 int:答案可达 10¹⁷,必须用 long long。
⚠️
忘记加 X 自身:分块只覆盖了"严格小于 X"的部分,X 本身要单独判断。
⚠️
特判缺失:i = 1(低位只有 0、1)与 i = 0(低位为空)不能套用 i ≥ 2 的公式。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(30)
空间复杂度
O(1)
r 最大
10⁹
运算量
常数级

时间怎么算的?

空间都用在哪?

只用几个变量。

✅ 常数级运算,瞬间完成。这正是题目"时限下调"想要的解法——复杂度与数据规模无关。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 数位统计的通用套路:把 [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¹⁸ 的位统计题
🌟
思考题:如果题目改成"求 [l, r] 中二进制含奇数个 1 的数的个数"(只要个数、不要和),代码要怎么改?(提示:更简单——只需把"块的和"换成"块的个数",即只累加 cnt,去掉 sumLow 和 pre 的部分。这说明"计数"是"求和"的简化版,而求和的难点在于要额外维护"这些数的值"。)