一、题目描述
输入输出格式
样例说明
数据范围
二、题目分析
1. 核心定义拆解
2. 问题本质
3. 数据范围分析
三、题目思路
思路 1：预生成所有幂和数 + 区间统计（最优）
步骤 1：生成所有可能的幂和数
步骤 2：统计区间内的数量
思路 2：逐数判断二进制 1 的个数
步骤 1：遍历区间内所有数
步骤 2：统计二进制中 1 的个数
步骤 3：输出总计数
两种思路对比
思路 | 优点 | 缺点 | 适用场景 |
预生成法 | 计算量极小，效率极高，代码简洁 | 需提前枚举所有可能的幂和数 | 本题数据范围，最优选择 |
逐数判断法 | 逻辑直观，无需预生成，扩展性强 | 需遍历最多 10^4 个数，计算量略大 | 数据范围更大、无法预生成的场景 |
四、C++ 代码实现
版本 1：预生成所有幂和数（推荐）
#include<iostream>#include<unordered_set>using namespace std;intmain(){// 1. 预生成所有可能的幂和数，存入集合去重unordered_set<int> s;for (int x = 0; x <= 13; x++) { // 2^13=8192 ≤ 10^4，2^14=16384>10^4for (int y = 0; y <= 13; y++) {int num = (1 << x) + (1 << y); // 等价于2^x + 2^yif (num <= 10000) { // 保证不超过数据范围上限s.insert(num);}}}// 2. 输入区间l, rint l, r;cin >> l >> r;// 3. 统计区间内的幂和数数量int ans = 0;for (int num : s) {if (num >= l && num <= r) {ans++;}}// 4. 输出结果cout << ans << endl;return 0;}
版本 2：逐数判断二进制 1 的个数
#include<iostream>using namespace std;// 统计n的二进制中1的个数intcountOne(int n){int cnt = 0;while (n > 0) {cnt += n & 1; // 取最低位，若为1则计数+1n >>= 1; // 右移一位}return cnt;}intmain(){int l, r;cin >> l >> r;int ans = 0;// 遍历区间内所有数for (int n = l; n <= r; n++) {int cnt = countOne(n);// 二进制1的个数为1或2，即为幂和数if (cnt == 1 || cnt == 2) {ans++;}}cout << ans << endl;return 0;}
五、考察知识点
1. 位运算基础
2. 集合的去重特性
3. 枚举法的应用
4. 数学本质理解
六、总结
文章来源：
四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！
