试题要求
对于一个正整数 ，我们将其转换为不含前导零的二进制表示,如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。例如，9 的二进制表示为(1001)2 ，是二进制回文数； 12的二进制表示为 (1100)2，不是二进制回文数。 你的任务是：给定一个正整数 ，计算在1 到 n 的范围内二进制回文数的数量。
输入格式
输入一行，包含一个正整数 。
输出格式
输出一行，包含一个数，表示在 到 的范围内二进制回文数的数量。
输入样例
15
输出样例
6
样例解释
样例 1 中，1 到 15 范围内 1、3 、5 、7 、9 、15 是二进制回文数。
数据范围：
$1\leq n\leq 10^5$
试题解析
一、题目在说什么？
题目给我们一个正整数 n，要求统计：
从
1到n之间，有多少个数的二进制表示是“回文”的。
什么叫二进制回文数？ 先把一个整数转换成二进制，然后看这个二进制字符串是不是左右对称。 例如：
9 的二进制是 1001
从左往右读是：
1001
从右往左读也是：
1001
所以 9 是二进制回文数。
再看：
12 的二进制是 1100
反过来是：
0011
不一样，所以 12 不是二进制回文数。
二、样例为什么输出 6？
输入：
15
我们检查 1 到 15。
| 十进制 | 二进制 | 是否回文 |
|---|---|---|
| 1 | 1 | 是 |
| 2 | 10 | 否 |
| 3 | 11 | 是 |
| 4 | 100 | 否 |
| 5 | 101 | 是 |
| 6 | 110 | 否 |
| 7 | 111 | 是 |
| 8 | 1000 | 否 |
| 9 | 1001 | 是 |
| 10 | 1010 | 否 |
| 11 | 1011 | 否 |
| 12 | 1100 | 否 |
| 13 | 1101 | 否 |
| 14 | 1110 | 否 |
| 15 | 1111 | 是 |
所以符合条件的是：
1, 3, 5, 7, 9, 15
一共有 6 个，因此输出：
6
三、解题思路
这道题的数据范围是：
1 ≤ n ≤ 100000
n 最大只有十万，不算特别大。
所以我们可以直接从 1 枚举到 n，每个数都做两件事：
- 把这个数转换成二进制字符串；
- 判断这个二进制字符串是不是回文。
如果是回文，答案就加 1。
四、如何把十进制转成二进制？
比如我们要把 9 转成二进制。
可以不断除以 2，记录余数：
9 ÷ 2 = 4 余 1
4 ÷ 2 = 2 余 0
2 ÷ 2 = 1 余 0
1 ÷ 2 = 0 余 1
余数从下往上读，就是：
1001
在程序中，我们可以这样写：
string toBinary(int x) {
string s = "";
while (x > 0) {
int r = x % 2;
s += char('0' + r);
x /= 2;
}
reverse(s.begin(), s.end());
return s;
}
这里要注意：
我们一开始得到的余数顺序是反的，所以最后要 reverse 一下。
五、如何判断一个字符串是不是回文？
比如：
1001
我们可以用两个指针：
左指针 l 指向开头
右指针 r 指向结尾
然后不断比较：
s[l] 是否等于 s[r]
如果有一次不相等，就说明不是回文。 如果一直都相等，就是回文。
代码如下：
bool isPalindrome(string s) {
int l = 0;
int r = s.size() - 1;
while (l < r) {
if (s[l] != s[r]) {
return false;
}
l++;
r--;
}
return true;
}
六、完整代码
#include <bits/stdc++.h>
using namespace std;
string toBinary(int x) {
string s = "";
while (x > 0) {
int r = x % 2;
s += char('0' + r);
x /= 2;
}
reverse(s.begin(), s.end());
return s;
}
bool isPalindrome(string s) {
int l = 0;
int r = s.size() - 1;
while (l < r) {
if (s[l] != s[r]) {
return false;
}
l++;
r--;
}
return true;
}
int main() {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
string b = toBinary(i);
if (isPalindrome(b)) {
ans++;
}
}
cout << ans << endl;
return 0;
}
七、复杂度分析
n 最大是 100000。
一个数转换成二进制后，长度大约是 log₂n。
因为：
100000 的二进制长度不到 20 位
所以每个数最多处理大约 20 个字符。 总时间复杂度大约是：
O(n log n)
对于 n ≤ 100000 来说，完全可以通过。
八、这道题的核心
这道题并不难，关键是理解三个概念：
- 二进制表示：把十进制数转换成只含
0和1的形式； - 回文：正着读和反着读一样；
- 枚举：从
1到n一个一个检查。
所以整体思路就是：
枚举每个数 → 转成二进制 → 判断是否回文 → 统计数量
这是一道非常适合练习“进制转换”和“字符串判断”的题目。