回文判断：正着读、反着读都一样¶

什么是回文？¶

121、1221、7 都是回文，123、120 不是。

单个数字也是回文；本教程把非负整数 0 也看作回文。负数、前导零是否参与比较，要看题意。本页的整数例子不处理负数，也不保留前导零。

方法一：把整数反过来，再和原数比较¶

例如 1221 反转后还是 1221，所以是回文；120 反转后是 21，所以不是。

一定要保留原数 n，用副本 x 拆数位。否则拆完变成 0，就没法正确比较了。

本例输入范围为 0 <= n <= 10^9，用 long long 存反转结果。输出 Yes 或 No。

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long x = n, reversed = 0;
    while (x > 0) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    if (reversed == n) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

输入 1221 输出 Yes；输入 120 输出 No；输入 0 输出 Yes。

如果数太大，反转结果可能超出整数范围；即使原数能放进 long long，反转后也未必能放下。大数请选择下面的字符串方法。

方法二：左右两端，一对一对比较¶

先学过字符串再看这一节。

把输入当作一串字符，不做加减乘除。左边的 left 从开头出发，右边的 right 从末尾出发：

两边字符不同，立刻确定不是回文。
相同，就都向中间移动一步。
相遇或交错时还没发现不同，就是回文。中间单独一个字符不用比较。

下面约定输入一个长度为 1 到 100000 的非空数字串，不含空格，保留所有前导零。

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

int main() {
    string s;
    cin >> s;
    int left = 0;
    int right = static_cast<int>(s.size()) - 1;
    bool ok = true;
    while (left < right) {
        if (s[left] != s[right]) {
            ok = false;
            break;
        }
        left++;
        right--;
    }
    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

ok ? "Yes" : "No" 表示：ok 为真时选择 "Yes"，否则选择 "No"，也可以换成前例的 if / else。

输入 010 会输出 Yes。如果把 010 当十进制整数读入，数值是 10，则不是回文。这就是“比较数字串”和“比较整数”不同的地方。

两种方法检查的次数都随位数增长，时间复杂度为 O(d)。整数反转用 O(1) 额外空间；字符串方法需要保存 O(d) 个字符，但不会发生反转整数的溢出。

二进制回文：先换一种写法，再判断¶

这里问的是：一个非负整数写成二进制以后，是不是回文？不是判断它的十进制写法。

约定使用不补前导零的二进制表示，0 表示为 "0"。不是拿固定 32 位或 64 位补零后的机器表示来比较。

十进制整数	二进制写法	二进制是否回文
0	0	是
5	101	是
6	110	否
9	1001	是
10	1010	否

怎样得到二进制的每一位？¶

十进制拆位是 % 10 和 /= 10；二进制拆位换成 % 2 和 /= 2。

例如 6：余数依次是 0、1、1，这是从低位到高位的顺序；倒过来写才是正常的二进制 110。详见二进制。

完整程序¶

输入 0 <= n <= 10^9。先收集余数，反转得到二进制串，再从两端比较。

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

int main() {
    long long n;
    cin >> n;
    string bits;
    do {
        int digit = n % 2;
        bits += char('0' + digit); // 把数值 0 或 1 变成字符 '0' 或 '1'
        n /= 2;
    } while (n > 0);
    reverse(bits.begin(), bits.end()); // 整串反转，得到正常读写顺序

    int left = 0;
    int right = static_cast<int>(bits.size()) - 1;
    bool ok = true;
    while (left < right) {
        if (bits[left] != bits[right]) {
            ok = false;
            break;
        }
        left++;
        right--;
    }
    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

bits += ... 表示在字符串末尾添加一个字符。reverse 来自 <algorithm>，这里把整个字符串反过来。若想看转换结果，可以在判断前临时加一行 cout << bits << '\n';；提交只要求 Yes/No 的题时要删掉这行调试输出。

不要把二进制数字拼成一个十进制整数来存，例如把二进制 100000000000000000000 存成“十进制大整数”：很容易溢出。字符串更合适。

自测：先算再运行¶

十进制整数 10 和数字串 010 的回文判断结果一样吗？
21 是十进制回文吗？它的二进制写法是 10101，是二进制回文吗？
判断数字串 1231 时，第一对字符相等，能马上输出 Yes 吗？

答案

不一样：前者不是，后者是。
十进制不是，二进制是。进制不同，答案可能不同。
不能；还要比较里面的 2 和 3，它们不相等。

想统计一个小区间有多少个回文数？先学枚举，再对每个候选数做一次回文判断。