GESP C++三级真题精讲：二进制回文串的两种解法与位运算技巧

2026年3月的GESP三级考试中，考察了一道结合了进制转换与回文判断的经典题目，题目编号为 luogu-B4499。其核心是判断一个正整数的二进制表示是否为回文串，并在给定范围内进行统计。对于正在准备C++三级考试或希望巩固基础算法的同学来说，这是一道不可多得的练手好题。

题目要求

题目描述

对于一个正整数 n，我们将其转换为不含前导零的二进制表示，如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。例如，3 的二进制表示为 11，是二进制回文数；4 的二进制表示为 100，不是二进制回文数。

你的任务是：给定一个正整数 n，计算在 1 到 n 的范围内二进制回文数的数量。

输入格式

输入一行，包含一个正整数 n。

输出格式

输出一行，包含一个数，表示在 1 到 n 的范围内二进制回文数的数量。

输入输出样例 #1

输入 #1

15

输出 #1

6

说明/提示

样例解释

样例 1 中，1 到 15 范围内 1、3、5、7、9、15 是二进制回文数。

数据范围
1 ≤ n ≤ 10^5

---

题目分析

这道题的核心思路非常清晰：我们需要遍历从 1 到 n 的每一个整数 i，然后判断 i 的二进制表示是否为回文串。如果是，则计数器加一。

问题的关键就落在了“如何判断一个整数的二进制表示是回文”上。这里我们介绍两种主流的思路，分别对应 GESP 三级的不同知识点要求。

思路一：传统数组与双指针法

这是最直接、最符合 GESP 三级对数组和循环考察要求的解法，分为两个步骤：

1. 十进制转二进制并存储： 对于待判断的整数 x，我们不断地执行 x % 2 取余数和 x / 2 整除操作（即“除2取余法”）。每次得到的余数（0或1）就是二进制位，我们可以按顺序存储在一个数组里。
2. 回文判断（双指针）： 存储完成后，我们得到了一个表示二进制序列（注意是逆序）的数组。利用双指针技巧，一个指针从数组头部开始，另一个从尾部开始，向中间移动并逐个比较对应位置的数字。若所有比较都相等，则为回文；否则不是。

这种方法逻辑清晰，直接运用了数组和循环控制，是解决此类问题的标准范式。

思路二：巧用位运算构造反转数

如果你对 C++ 的位运算有较好的掌握，这道题可以有一个非常巧妙且高效的解法，无需借助数组。

核心思想是：直接构造出原数二进制表示的反转数，然后比较两者是否相等。

我们可以想象这样一个过程：不断地“剥离”原数 x 的最低位（x & 1），并将其“拼接”到另一个数 reversed 的后面。通过 reversed = (reversed << 1) | (x & 1) 和 x >>= 1 这两步操作即可实现。当 x 被剥离为 0 时，reversed 就是原数二进制形式的完全反转。最后只需判断 原数 == reversed 即可。

这种方法代码更简洁，运算效率也更高，展现了位运算的魅力。

---

示例代码

解法一：数组存储与双指针比对（推荐）

这是最贴合三级考纲的写法，易于理解和实现。

#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;
}

解法二：位运算构造反转数

这种解法更为精炼，适合已经掌握位运算的同学进行拓展学习。

#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;
}

总结

通过这道 GESP 三级真题，我们不仅复习了“除2取余”的进制转换和经典的回文判断算法，还探索了利用位运算进行高效处理的技巧。在云栈社区，我们常常讨论如何将基础算法知识灵活运用到具体问题中。无论你选择哪种方法，理解其背后的逻辑并能够清晰实现，才是应对认证考试和提升编程能力的关键。大家可以尝试在洛谷题库 (luogu) 搜索题号 B4499 进行实际评测，验证自己代码的正确性。