二进制回文串 题解

题目分析

题目要求我们统计 $1$ 到 $n$ 之间有多少个“二进制回文数”。
一个数被称为二进制回文数，当且仅当它的二进制表示（不含前导零）是一个回文字符串，即从左往右读和从右往左读完全一致。

例如：

• $9$ 的二进制是 1001，正读反读都是 1001，是回文数；
• $12$ 的二进制是 1100，反读为 0011，不相等，不是回文数。

本题的数据范围很小：$n \le 10^5$，因此即便是最朴素的枚举判断方法也完全可以在时限内通过。

解题思路

由于 $n$ 最大只有 $10^5$，我们可以直接对 $1$ 到 $n$ 中的每一个整数进行判断：

1. 将当前整数转换为二进制，并保存每一位的值（0 或 1）；
2. 检查这个二进制数组是否左右对称（回文）；
3. 统计满足条件的数的个数。

这种方法虽然时间复杂度不是最优，但足以应对本题的数据范围，并且代码简单，容易实现和理解。

算法说明

我们可以将每个数 $x$ 用“除 $2$ 取余”的方法逐位提取其二进制位：

while x > 0:
    将 x % 2 存入数组
    x = x / 2

这样得到的是从低位到高位的二进制位序列。例如 $9$ 会得到 1, 0, 0, 1，其逆序恰好是通常的二进制写法 1001。不过因为回文要求正反读相同，低位到高位的序列与高位到低位的序列是否回文是等价的，因此直接用这个序列判断即可，无需颠倒。

判断回文：设置两个指针，一个指向数组开头，一个指向末尾，比较对应位置的数字是否相等，一旦发现不同，该数就不是回文数。

如果整个循环没有发现不相等的情况，则说明它是二进制回文数，计数器加一。

时间复杂度分析

对于每一个 $i$（$1 \le i \le n$）：

• 转换成二进制需要 $\lfloor \log_2 i \rfloor + 1$ 次除法和取余，即 $O(\log i)$ 步；
• 检查回文同样需要扫描 $O(\log i)$ 个元素。

因此单次判断的复杂度为 $O(\log n)$。
总的时间复杂度为 $O(n \log n)$。当 $n = 10^5$ 时，$\log_2 n \approx 17$，运算次数约为 $1.7 \times 10^6$，完全可以在 $1$ 秒内完成。

空间上我们只需要一个大小为 $50$ 左右的数组（$10^5$ 的二进制位不超过 $17$ 位），因此空间复杂度 $O(1)$。

参考代码解释

以下是题目给出的参考代码，我们对其关键部分进行说明：

cpp
复制
1#include <iostream>
2using namespace std;
3int main() {
4    int n, a[50] = {0}, ans = 0;
5    cin >> n;
6    for(int i = 1; i <= n; i++) {     // 枚举 1 到 n 的每个数
7        int t = i, pos = 0;
8        while(t) {                    // 将 t 的二进制位存入数组 a
9            a[pos++] = t % 2;
10            t /= 2;
11        }
12        bool ok = true;
13        for(int i = 0; i < pos; i++) // 检查是否为回文
14            if(a[i] != a[pos - i - 1]) {
15                ok = false;
16                break;
17            }
18        ans += ok;                   // 若是回文则 ans 加 1
19    }
20    cout << ans;
21    return 0;
22}

• a[50] 用于存储当前数字的二进制序列，足够存放 $10^5$ 以内的所有二进制位（最多 17 位）。
• while(t) 循环完成“取余存数组、除以 $2$”的过程，pos 记录位数。
• 回文判断中，a[i] 与 a[pos - i - 1] 进行比较：pos - i - 1 是与 i 对称位置的索引。只要发现一对数字不同，立即标记为不是回文并跳出循环。
• 最后 ans += ok：在 C++ 中，bool 值 true 可以隐式转换为 1，false 转换为 0，因此如果 ok 为真，ans 加 $1$。

拓展思考

本题由于 $n$ 不大，暴力枚举已足够。如果 $n$ 增大到 $10^{18}$ 甚至更大，就需要用构造回文串的方法来计算，通过枚举二进制回文串的“前半部分”，生成所有不超过 $n$ 的回文数并计数。但作为一道简单题，掌握暴力判断的方法并理解二进制转换与回文检测的逻辑就足够了。

总结

此题的核心知识点是：

• 整数与二进制的转换（除 $2$ 取余法）
• 回文字符串的判断（双指针法）

其代码量小，思路清晰，适合初学者练习循环和数组的基本操作。