针对“二进制回文串”问题，我们需要计算在区间 $[1, n]$ 内，有多少个正整数的二进制表示（不含前导零）是回文串。题目给定的数据范围是 $1 \leq n \leq 10^5$，这要求算法的时间复杂度应控制在 $O(n \log n)$ 或更优。

问题解构与算法分析

问题的核心在于判断一个正整数是否为二进制回文数。其标准流程为：

1. 转换为二进制字符串：将整数 $x$ 转换为其二进制表示，并去除可能的前导零（在标准 toBinaryString 等方法中，非零整数转换结果本身不含前导零）。
2. 回文判定：检查该二进制字符串是否与其反转字符串相同。

暴力枚举法是最直观的解法：遍历 $1$ 到 $n$ 的每个整数，执行上述两步判断，统计回文数个数。对于每个数，二进制转换和回文判定的时间复杂度为 $O(\log n)$，总复杂度为 $O(n \log n)$，在 $n=10^5$ 的约束下完全可行。

算法流程：

1. 读取输入的正整数 $n$。
2. 初始化计数器 count = 0。
3. 循环 i 从 1 到 n：
   • 将 i 转换为二进制字符串 binStr。
   • 判断 binStr 是否等于其反转字符串 reversedStr。
   • 若相等，则 count++。
4. 输出 count。

复杂度分析：

• 时间复杂度：$O(n \log n)$。遍历 $n$ 个数，每个数的二进制位数约为 $\log_2 n$，转换和比较操作与之线性相关。
• 空间复杂度：$O(\log n)$。主要开销在于存储每个数的二进制字符串。

代码实现与详细注释

以下是 C++ 语言的实现代码，包含两种常见方法：使用标准库函数进行回文判断，以及手动进行回文判断。

#include <iostream>
#include <bitset>
#include <algorithm>
#include <string>
using namespace std;

// 方法一：使用标准库函数判断回文
int countBinaryPalindromes_method1(int n) {
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        // 将整数转换为二进制字符串（bitset会自动处理前导零）
        string binStr = bitset<32>(i).to_string(); // 使用足够大的位数，如32
        // 去除前导零：找到第一个'1'的位置
        size_t firstOne = binStr.find('1');
        if (firstOne != string::npos) {
            binStr = binStr.substr(firstOne);
        } else {
            // 如果全为0（即i=0的情况，但i从1开始，所以不会进入此分支）
            binStr = "0";
        }
        // 判断是否为回文：比较字符串与其反转
        string reversedStr = binStr;
        reverse(reversedStr.begin(), reversedStr.end());
        if (binStr == reversedStr) {
            ++count;
        }
    }
    return count;
}

// 方法二：手动判断回文（更高效，避免字符串拷贝和反转）
int countBinaryPalindromes_method2(int n) {
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        // 获取二进制表示
        string binStr;
        int temp = i;
        while (temp > 0) {
            binStr.push_back((temp & 1) ? '1' : '0');
            temp >>= 1;
        }
        // 此时binStr是逆序的（最低位在前），需要反转一次得到正序
        reverse(binStr.begin(), binStr.end());
        
        // 手动判断回文
        bool isPalindrome = true;
        int left = 0, right = binStr.size() - 1;
        while (left < right) {
            if (binStr[left] != binStr[right]) {
                isPalindrome = false;
                break;
            }
            ++left;
            --right;
        }
        if (isPalindrome) {
            ++count;
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    
    // 两种方法任选其一
    // int result = countBinaryPalindromes_method1(n);
    int result = countBinaryPalindromes_method2(n);
    
    cout << result << endl;
    return 0;
}

代码要点解析：

1. 二进制转换：
   • 方法一：使用 bitset<32>(i).to_string() 将整数转换为固定32位的二进制字符串，然后通过 find('1') 和 substr 去除前导零。这种方法简单直观，但会产生额外的字符串操作开销。
   • 方法二：通过循环和位运算（temp & 1 和 temp >>= 1）手动构建二进制字符串。注意，这样得到的字符串是逆序的（最低位在前），因此需要调用 reverse 一次得到正序。这种方法避免了查找前导零的步骤，通常更高效。
2. 回文判断：
   • 方法一：使用 reverse 函数生成反转字符串，然后直接比较。代码简洁，但需要创建反转字符串的副本。
   • 方法二：使用双指针法，从字符串两端向中间遍历比较。只需一次遍历，空间复杂度为 $O(1)$，是更优的选择。
3. 效率考量：对于 $n=10^5$，两种方法均能轻松通过。方法二在字符串操作上更节省，推荐在实际竞赛中使用。

运行示例与场景扩展

以样例输入 n = 15 为例，程序的执行过程如下：

1. 输入 15。
2. 遍历 i 从 1 到 15：
   • i=1：二进制 "1"，是回文。
   • i=2：二进制 "10"，不是回文。
   • i=3：二进制 "11"，是回文。
   • i=4：二进制 "100"，不是回文。
   • i=5：二进制 "101"，是回文。
   • i=6：二进制 "110"，不是回文。
   • i=7：二进制 "111"，是回文。
   • i=8：二进制 "1000"，不是回文。
   • i=9：二进制 "1001"，是回文。
   • i=10：二进制 "1010"，不是回文。
   • i=11：二进制 "1011"，不是回文。
   • i=12：二进制 "1100"，不是回文。
   • i=13：二进制 "1101"，不是回文。
   • i=14：二进制 "1110"，不是回文。
   • i=15：二进制 "1111"，是回文。
3. 统计得到回文数个数为 6，输出结果与样例一致。

为了更深入地理解二进制回文数的分布，我们可以分析其数学特性。二进制回文数与对称性紧密相关。对于一个 $k$ 位的二进制数，如果它是回文数，那么其二进制串的前 $\lceil k/2 \rceil$ 位决定了整个数。例如，所有3位二进制回文数为： 101(5)、 111(7)。所有4位二进制回文数为： 1001(9)、 1111(15)。这种特性可以用于构造法生成所有不超过 $n$ 的二进制回文数，从而将时间复杂度降低到 $O(\sqrt{n} \log n)$ 或更好，但这超出了本题暴力法的范畴。

算法思想总结与扩展

本题是数制转换与字符串处理的结合，主要考查以下能力：

1. 进制转换：熟练掌握整数到二进制字符串的转换方法。
2. 回文判断：掌握字符串回文判断的多种实现（反转比较、双指针法）。
3. 边界处理：注意二进制表示不含前导零的要求。

扩展思考：

• 更大数据范围：如果 $n$ 增大到 $10^9$ 甚至更大，暴力枚举将不可行。此时需要利用二进制回文数的构造规律进行计数。例如，可以按二进制位数分组，对于长度为 $len$ 的二进制回文数，其前一半（$\lceil len/2 \rceil$ 位）可以任意取（但不能全为0），从而计算出该长度下的回文数个数，再累加所有长度不超过 $\lfloor \log_2 n \rfloor + 1$ 且对应数值不超过 $n$ 的回文数。
• 其他进制回文：问题可以推广到判断任意进制（如十进制、八进制、十六进制）下的回文数。只需将转换基数从2改为目标进制即可。
• 同时是多种进制回文的数：寻找同时是二进制和十进制回文的数（如1, 3, 5, 7, 9, 33, 99等）。这需要多一层进制转换和回文判断。

通过解决此题，可以巩固循环、位运算、字符串操作等基础编程技能，并为处理更复杂的数论与字符串结合问题打下基础。