【GESP】C++三级真题 luogu-B4499, [GESP202603 三级] 二进制回文串
2026年3月，GESP三级真题，考察十进制转二进制与回文判断，难度★★☆☆☆。
B4499 [GESP202603 三级] 二进制回文串
题目要求
题目描述
对于一个正整数 $n$，我们将其转换为不含前导零的二进制表示，如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。例如，$9$ 的二进制表示为 $(1001)_2$，是二进制回文数；$12$ 的二进制表示为 $(1100)_2$，不是二进制回文数。
你的任务是：给定一个正整数 $n$，计算在 $1$ 到 $n$ 的范围内二进制回文数的数量。
输入格式
输入一行，包含一个正整数 $n$。
输出格式
输出一行，包含一个数，表示在 $1$ 到 $n$ 的范围内二进制回文数的数量。
输入输出样例 #1
输入 #1
1
15
输出 #1
1
6
说明/提示
样例解释 样例 1 中，$1$ 到 $15$ 范围内 $1$、$3$、$5$、$7$、$9$、$15$ 是二进制回文数。
数据范围 $1 \le n \le 10^5$。
题目分析
这道题考察了两个重要且经典的知识点：进制转换与回文判断。GESP 三级对数组的掌握有了明确的要求，这道题恰好可以把这些点结合起来。
题目的核心是遍历 $1$ 到 $n$ 的每一个数字，然后判断该数字是不是“二进制回文数”。如果是，计数器就加一，最后输出计数器的值。
如何判断一个整数是不是“二进制回文数”呢？
三级传统解法
- 转二进制并提取各位数字： 对于一个十进制数，我们可以不断地对 2 实行“求余”和“整除”操作（也就是“除2取余法”），每次取出的余数就是二进制下该位的值。我们可以用一个整数数组（比如
int bin[40]）把这些提取出来的余数依次存起来。 - 回文判断： 提取完成后，这个数组里存放的就是该数转换出的二进制序列的逆序（先求出的是最低位）。但巧妙的是，“回文”的定义正着读和反着读都完全一样，所以我们就算存的是个逆序数组，也不影响回文的判定。我们使用“双指针”的办法，一个从数组的头（下标 0）开始，一个从数组的尾（下标 len - 1）开始，两头向中间靠拢，一一比对。只要有不一样的地方，就说明不是回文；如果直到中间都完全一样，那就是回文。
由于在 GESP 三级考纲中，尚未要求掌握自定义函数，我们在处理每位数字时，可直接将上述判定逻辑内嵌在主循环中完成。
拓展解法（位运算）
如果熟练运用 C++ 的位运算（Bitwise Operations），这道题能够做到甚至不借用任何数组，仅在原数字上进行“变魔术”就能判断出结果。位运算也在 GESP 三级考纲中有明确要求，但通常使用的较少切容易被忽略，但本体使用起来非常巧妙。
我们可以想办法“捏造”出一个新的反转数字 reversed。就像组装十进制数字一样（个位乘1，十位乘10），这次我们在二进制的维度中组装它。只需要不断地把已有的翻转数字通过 << 1 左移腾出空间，然后“贴上”原数最末尾的那一位（也就是 x & 1），最后将原数 >> 1（右移）用来抛弃已经被处理过的低位。当这个过程重复完毕，直接拿还原出倒转数字和原数对比即可。非常简洁！
示例代码
传统解法（推荐）
按照上述分析，使用“数组存储二进制各位”结合“首尾双指针比对”是十分符合 GESP 三级大纲要求的经典解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
int main() {
int n;
std::cin >> n;
int count = 0; // 用于统计回文数的数量
// 从 1 到 n 挨个检查
for (int i = 1; i <= n; i++) {
int x = i;
int bin[40]; // 准备一个数组用来存放数字的二进制位，10^5 足够用了
int len = 0; // 记录二进制的位数
// 不断地进行除 2 取余，将生成的二进制位存入数组
while (x > 0) {
bin[len] = x % 2;
x = x / 2;
len++;
}
// 双指针进行回文判断
bool is_palindrome = true;
// j 从 0 开始往后走，k 从末尾往前走，直到两者相遇或者错过
for (int j = 0, k = len - 1; j < k; j++, k--) {
if (bin[j] != bin[k]) {
// 只要有一对不同，这就绝不可能是回文串
is_palindrome = false;
break;
}
}
// 如果经受住了所有比对，那就是回文串
if (is_palindrome) {
count++;
}
}
std::cout << count << std::endl;
return 0;
}
拓展解法（位运算）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
bool isBinaryPalindromeBitwise(int x) {
int original = x; // 记录下它原本的值，等下用来最终比较
int reversed = 0; // 用来一点一点组装倒排序后的数字
while (x > 0) {
// reversed << 1 表示把已组装的数字整体左移（类似于十进制乘 10）
// x & 1 取出最低位对应的二进制位（0 或 1，等同于 % 2）
// | (按位或) 也就是把那一位“拼接”在最低位空白处
reversed = (reversed << 1) | (x & 1);
// x >>= 1 表示被取光的最末位可以丢弃了（类似于十进制除 10）
x >>= 1;
}
// 翻转重建后的数如果和原数相等，那就是天然的回文数啦！
return original == reversed;
}
int main() {
int n;
std::cin >> n;
int count = 0;
for (int i = 1; i <= n; i++) {
if (isBinaryPalindromeBitwise(i)) {
count++;
}
}
std::cout << count << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
