给定正整数 n,统计 1 到 n 中有多少个数,其二进制表示正读反读都一样。
对于一个正整数 n,将其转换为不含前导零的二进制表示。如果这个二进制序列从左向右读与从右向左读完全相同,则称该数为二进制回文数。例如 9 的二进制是 (1001)₂,是二进制回文数;12 的二进制是 (1100)₂,不是。
你的任务是:给定正整数 n,计算 1 到 n 范围内二进制回文数的数量。
进制转换回文判断枚举计数去前导零
| 项目 | 说明 |
|---|---|
| 输入 | 一行一个正整数 n |
| 输出 | 1 到 n 中二进制回文数的个数 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 二进制长度 | 最多 17 位(2¹⁶ = 65536,2¹⁷ = 131072) |
题目给的样例答案 6,我们亲手把它算出来,确认理解没跑偏。
只有一位,正读反读都是 1
✅ 是回文(计数 1)
2 的二进制 10,反转成 01,与原串不同
3 的二进制 11,反转还是 11
❌ 2 不算,✅ 3 算(计数 2)
100 反转 001 ≠ 100
101 反转 101 = 101
110 反转 011 ≠ 110
只有 5 算(计数 3)
三位全是 1,反转不变
✅ 算(计数 4)
8 = 1000 ❌;9 = 1001 ✅
10 = 1010 ❌,11 = 1011 ❌,12 = 1100 ❌
13 = 1101 ❌,14 = 1110 ❌
这一段只有 9 算(计数 5)
四位全是 1
✅ 算(计数 6)
| 数字 | 二进制 | 是否回文 |
|---|---|---|
| 1 | 1 | ✅ 是 |
| 2 | 10 | ❌ 否 |
| 3 | 11 | ✅ 是 |
| 4 | 100 | ❌ 否 |
| 5 | 101 | ✅ 是 |
| 6 | 110 | ❌ 否 |
| 7 | 111 | ✅ 是 |
| 8 | 1000 | ❌ 否 |
| 9 | 1001 | ✅ 是 |
| 10 ~ 14 | — | ❌ 都不是 |
| 15 | 1111 | ✅ 是 |
对 1 到 n 每个数求二进制串,反转后比较
枚举二进制长度 k,前半段自由取,后半段镜像过来,判断是否 ≤ n
| n 的规模 | 枚举法运算量 | 构造法运算量 |
|---|---|---|
| 1,000 | 约 1 万次 | 约 60 次 |
| 10,000 | 约 14 万次 | 约 200 次 |
| 100,000(本题上限) | 约 170 万次 | 约 500 次 |
输入一串数字(空格或逗号分隔),逐个转成二进制并判断是否回文,最后统计回文个数。
点按钮开始 →
#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; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 都省了。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
1 | 1 | 最小规模,1 位必是回文 |
2 | 1 | 2 = 10 不是回文 |
3 | 2 | 1 和 3 |
7 | 4 | 1、3、5、7 —— 注意不是 5 个 |
9 | 5 | 第一个四位回文数 1001 出现 |
15 | 6 | 题面给出的样例 |
100000 | 运行验证 | 最大规模,考察是否超时 |
i = 0 会把 0 也算进去(0 的二进制是 "0",也"回文")。只需要一个字符串保存当前数字的二进制(最长 17 个字符),所以是 O(log n),与 n 无关。
✅ n = 10⁵ 时总操作约 170 万次,C++ 一瞬间跑完,稳妥通过。
// 十进制转二进制(正序) 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 逐个数,满足就累加 | 统计类题目、筛法类题目 |