A106098 二进制回文串 题解

题意

给出一个数字 $n$，求 $1$~$n$ 范围内，有多少数字的二进制表示是回文的。

解析

这里讲解重点部分。

1. 二进制表示

在本题中，得到数字二进制可以有两种方法：十进制转二进制和二进制自增。

方法 1：十进制转二进制

十进制转换成二进制通常是利用短除法，依次除以 $2$ 取余数，再把余数反向拼接得到。例如 $15$，它转换成二进制的过程是这样的：

 2 |   15
   ----------
   2 |   7     ... 1  ↑
     --------         |
     2 |  3    ... 1  |
       ------         |
       2 | 1   ... 1  |
         ----         |
           0   ... 1  |

所以，$(15)_{10}=(1111)_{2}$。

参考代码：

string to_bin(int x) {
    string b;
    while(x) {
        b = (x % 2 ? "1" : "0") + b; // 除以 2 取余
        // 需要反转，所以加在字符串前面
        x /= 2; // 除以 2
    }
    return b;
}

方法 2：二进制自增

定义 string 类型的变量 bin，存储数字的二进制表示，初始化为 "0"。

然后，先自增，再判断，如果 bin 是回文的，那么答案加 $1$。

首先是自增。二进制自增可以这样做：

观察下面这个二进制数：

$$(10100111)_{2}$$

这个数加 $1$ 后的值应该是：

$$(10101000)_{2}$$

那么，我们就可以得到二进制自增的方法：

· 找到最右边的 $0$，将它修改为 $1$。

$$(1010\textcolor{lightgreen}{1}111)_{2}$$

· 然后将这个 $0$ 右边的所有 $1$ 修改为 $0$。（当然，如果这个 $0$ 是最右边的一位就可以忽略这一步）

$$(10101\textcolor{lightgreen}{000})_{2}$$

但是还有一种特殊情况。例如：

$$(111111)_{2}$$

可以发现这里面并没有 $0$。所以，我们需要将所有位都修改为 $0$。

$$(\textcolor{lightgreen}{000000})_{2}$$

再在最高位加入 $1$。

$$(\textcolor{lightgreen}{1}000000)_{2}$$

这样，也成功处理了这种特殊情况。

参考代码：

void plus1() {
    int i = bin.length()-1;
    for(;i >= 0;i--) { // 因为从最右边开始所以要倒序查找
        if(bin[i] == '1') // 如果这一位是 1
            bin[i] = '0'; // 修改成 0
        else { // 否则，如果这一位是 0
            bin[i] = '1'; // 修改成 1
            break; // 退出循环
        }
    }
    if(i == -1)  // 如果找了一遍下来没找到 0，此时 i 应该为 -1
        bin = "1" + bin; // 在开头插入一个 1
}

然后就是判断了。判断很简单，双指针从两边到中间遍历即可。

参考代码：

bool check() {
    int len = bin.length();
    for(int i = 0;i <= len;i++) // 左边的指针
        if(bin[i] != bin[len-i+1]) // 右边的指针就是 len-i+1
            return 0; // 如果检测到不相等的位就返回不是回文的
    return 1; // 如果没检测到不相等的位就是回文的
}

代码

这里展示的代码对于处理二进制采用的是二进制自增。

#include <iostream>
#include <string>

using namespace std;

string bin = "0"; // bin 存储二进制数字

// 判断当前的二进制是不是回文的
bool check() {
    int len = bin.length();
    for(int i = 0;i < len;i++) 
        if(bin[i] != bin[len-i-1]) 
            return 0;
    return 1;
}
// 二进制加 1 的函数
void add1() {
    int i,len = bin.length();
    for(i = len-1;i >= 0;i--) {
        if(bin[i] == '1') 
            bin[i] = '0';
        else {
            bin[i] = '1';
            break;
        }
    }
    if(i == -1) 
        bin = "1" + bin;
}

int main() {
    int n,cnt = 0;cin >> n;
    for(int num = 1;num <= n;num++) {
        add1();
        if(check()) cnt++;
    }
    cout << cnt;
    return 0;
}

后记

可以点个赞吗