GESP 题解库 / 3 级题解 / [GESP202603 三级] 二进制回文串 · 第 1 / 28 题
GESP202603 三级 · B4499 · 简单

二进制回文串

给定正整数 n,统计 1 到 n 中有多少个数,其二进制表示正读反读都一样。

📊
n ≤ 10⁵
数据规模
🔢
int
数值类型
⚡
O(n log n)
时间复杂度
🎯
枚举 + 进制转换
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

对于一个正整数 n,将其转换为不含前导零的二进制表示。如果这个二进制序列从左向右读与从右向左读完全相同,则称该数为二进制回文数。例如 9 的二进制是 (1001)₂,是二进制回文数;12 的二进制是 (1100)₂,不是。

你的任务是:给定正整数 n,计算 1 到 n 范围内二进制回文数的数量。

💡
人话翻译:把 1 到 n 每个数都写成二进制,看看哪些数的二进制串正读反读一样,数一数有几个。注意叶子级的细节:二进制首位必定是 1,不存在前导零。

🔍 关键词提取

进制转换回文判断枚举计数去前导零

已知条件

项目说明
输入一行一个正整数 n
输出1 到 n 中二进制回文数的个数
数据范围1 ≤ n ≤ 10⁵
二进制长度最多 17 位(2¹⁶ = 65536,2¹⁷ = 131072)

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 二进制回文串计数
📥 输入与循环
读入 n
i 从 1 枚举到 n
计数器 ans 置 0
每个数独立判断
🔄 进制转换
除 2 取余法
余数拼成 0/1 串
循环条件 x > 0
得到的串恰好低位在前
🔍 回文判定
反转字符串比较
或双指针从两端夹
也可直接用数字反转
回文反转后不变
⚠️ 边界细节
1 是回文(一位数)
循环从 i = 1 开始
不含前导零
int 足够,不会溢出
03
样例手算推导
把 n = 15 从头算一遍

🧮 逐个数字验证 n = 15

题目给的样例答案 6,我们亲手把它算出来,确认理解没跑偏。

1
1 → 1

只有一位,正读反读都是 1

✅ 是回文(计数 1)

2
2 → 10,3 → 11

2 的二进制 10,反转成 01,与原串不同

3 的二进制 11,反转还是 11

❌ 2 不算,✅ 3 算(计数 2)

3
4 → 100,5 → 101,6 → 110

100 反转 001 ≠ 100

101 反转 101 = 101

110 反转 011 ≠ 110

只有 5 算(计数 3)

4
7 → 111

三位全是 1,反转不变

✅ 算(计数 4)

5
8 → 1000,9 → 1001,10 ~ 14

8 = 1000 ❌;9 = 1001 ✅

10 = 1010 ❌,11 = 1011 ❌,12 = 1100 ❌

13 = 1101 ❌,14 = 1110 ❌

这一段只有 9 算(计数 5)

6
15 → 1111

四位全是 1

✅ 算(计数 6)

📊 汇总

数字二进制是否回文
11✅ 是
210❌ 否
311✅ 是
4100❌ 否
5101✅ 是
6110❌ 否
7111✅ 是
81000❌ 否
91001✅ 是
10 ~ 14—❌ 都不是
151111✅ 是

🔍 观察到的规律

04
解法对比
暴力枚举就够用,无需高级技巧

⚔️ 解法对比

🟢 枚举 + 除 2 取余 推荐

对 1 到 n 每个数求二进制串,反转后比较

  • 时间复杂度 O(n log n)
  • 每个数二进制最多 17 位
  • n = 10⁵ 时运算量约 170 万次
  • 代码十几行,不容易写错
💡
为什么够用:C++ 每秒能跑约 10⁸ 次操作,170 万次不到 1 毫秒。

🔵 按位数构造回文数

枚举二进制长度 k,前半段自由取,后半段镜像过来,判断是否 ≤ n

  • 时间复杂度 O(√n)
  • 不需要逐个数字转换
  • 代码约 40 行,边界多
  • n 达到 10¹⁸ 时才有必要
⚠️
风险提示:要处理长度奇偶、前导位必须是 1、末尾数是否超过 n 等细节,三级考试写它性价比极低。

📈 性能对比

n 的规模枚举法运算量构造法运算量
1,000约 1 万次约 60 次
10,000约 14 万次约 200 次
100,000(本题上限)约 170 万次约 500 次
05
算法流程图
一次除法循环 + 一次反转比较
开始读入 n,ans = 0i 从 1 枚举到 n把 i 转成二进制串 binbin 是回文吗?是 ✓ans++否 ✗不计数i 还没到 n 吗?输出 ans结束i++ 回到循环继续检查
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 二进制回文检查器

输入一串数字(空格或逗号分隔),逐个转成二进制并判断是否回文,最后统计回文个数。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

// 判断整数 x 的二进制表示是否为回文
bool isBinPalindrome(int x) {
    string b = "";
    while (x > 0) {              // 除 2 取余,得到 0/1 位
        b += char('0' + x % 2);
        x /= 2;
    }
    string r = b;
    reverse(r.begin(), r.end()); // 反转后比较
    return b == r;
}

int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (isBinPalindrome(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
🤔
为什么"低位在前"也不影响?除 2 取余得到的是低位在前的串,但回文串本身反转后不变,所以正序存还是逆序存,比较的结果一样。

📖 关键几行怎么看

代码作用为什么这样写
while (x > 0)不断取下一位x 变成 0 说明所有位都取完了
char('0' + x % 2)把 0/1 变成字符字符 0 的 ASCII 码加上余数就是 "0" 或 "1"
reverse(r.begin(), r.end())反转字符串需要 <algorithm>(bits/stdc++.h 已包含)
return b == r;判断相等string 支持直接 == 比较
⚡
省空间写法:不用字符串,边取余边构造反转后的数字,最后比 orig == rev 即可,连 string 都省了。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
11最小规模,1 位必是回文
212 = 10 不是回文
321 和 3
741、3、5、7 —— 注意不是 5 个
95第一个四位回文数 1001 出现
156题面给出的样例
100000运行验证最大规模,考察是否超时
✅
自查清单:① 循环区间是不是 1 ~ n?② 二进制串有没有前导零?③ 比较的是"反转后是否相等"而不是"是否全为 1"?

🚨 易错点清单

⚠️
循环从 0 开始:题目要求统计 1 到 n,写成 i = 0 会把 0 也算进去(0 的二进制是 "0",也"回文")。
⚠️
把"二进制长度"当成固定位数:题目明确说不含前导零,不能把 25(11001)补成 00011001 再判回文。
⚠️
用了 int 却想要更大的 n:本题 n ≤ 10⁵,int 足够;但如果数据放大到 10⁹,单个数的二进制就有 30 位,仍不溢出,只是枚举法会超时。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(log n)
n 最大
10⁵
运算次数
约 170 万

时间怎么算的?

空间都用在哪?

只需要一个字符串保存当前数字的二进制(最长 17 个字符),所以是 O(log n),与 n 无关。

✅ n = 10⁵ 时总操作约 170 万次,C++ 一瞬间跑完,稳妥通过。

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

🔗 常用技巧小抄

// 十进制转二进制(正序)
string toBinary(int x) {
    string s = "";
    while (x > 0) { s = char('0' + x % 2) + s; x /= 2; }
    return s.empty() ? "0" : s;
}

// 通用回文判断(双指针)
bool isPal(const string &s) {
    for (int i = 0, j = (int)s.size() - 1; i < j; i++, j--)
        if (s[i] != s[j]) return false;
    return true;
}

// 数 1 的个数(本题不直接用,但很常用)
int cnt1(int x) { int c = 0; while (x) { c += x & 1; x >>= 1; } return c; }

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
除 k 取余法把 i 转成二进制串任意进制转换、进制判断
回文判定反转后比较或双指针字符串回文、数字回文、回文子串
枚举 + 计数1 ~ n 逐个数,满足就累加统计类题目、筛法类题目
🌟
思考题:如果 n 放大到 10⁹,枚举法就太慢了。能不能换个角度——直接构造二进制回文数?提示:先定长度 k,前 ⌈k/2⌉ 位自由取(首位必须是 1),后一半镜像过去,再看这个数是否 ≤ n。