题解 | 10进制 VS 2进制

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

vector<int> div(vector<int>a, int b, int& r) {
    //用引用返回余数，返回的是商
    int t = 0;//代表余数
    vector<int>c;
    //除法要倒着算
    for (int i = a.size() - 1; i >= 0; i--) {
        int tmp = (t * 10 + a[i]) / b;
        c.push_back(tmp);
        t = (t * 10 +a[i]) % b;
    }
    r = t;
    //反转，然后去除前导0,由于还要进行试除法，所以最后一个0也得把他清空
    reverse(c.begin(), c.end());
    while (c.size() >= 1 && c.back() == 0)c.pop_back();
    return c;
}

//其实就是要实现秦九韶算法
//得到二进制数后还要实现大整数乘法+大整数加法
vector<int> multiply(vector<int>a, int b) {
    int t = 0;
    vector<int>c;
    //高精度乘法，乘完之后要把进位进完才行
    for (int i = 0; i < a.size()||t; i++) {
        if(i<a.size())
            t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    //去除前导0
    while (c.size() > 1 && c.back() == 0)c.pop_back();
    return c;
}

//长整数和短整数的加法
vector<int> add(vector<int>a, int b) {
    int t = b;
    vector<int>c;
    //高精度乘法，乘完之后要把进位进完才行
    for (int i = 0; i < a.size() || t; i++) {
        if (i < a.size())
            t += a[i];
        c.push_back(t % 10);
        t /= 10;
    }
    //去除前导0
    while (c.size() > 1 && c.back() == 0)c.pop_back();
    return c;
}
//位运算
int main() {
    //由于存不下，只能用大整数除法
    string str;
    cin >> str;
    vector<int>mid;
    vector<int> a;
    int b = 2;//代表要转换为二进制数
    for (int i = str.size()- 1; i >= 0; i--) {
        a.push_back(str[i]-'0');
    }
    /*int r = 0;
    res = div(a, 2, r);
    for (int i = res.size() - 1; i>=0; i--) {
        cout << res[i];
    }*/
    int r = 0;
    //短除法
    while (!div(a, 2, r).empty()) {
        mid.push_back(r);
        a = div(a, 2, r);
    }
    mid.push_back(r);


    /*res = multiply(res, 10);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }*/
    //秦九韶算法
    vector<int> res = { 0 };
    for (int i = 0; i < mid.size(); i++) {
        res = add(multiply(res, 2),mid[i]);
    }
    for (int i = res.size()-1; i >=0; i--) {
        cout << res[i];
    }

}
// 64 位输出请用 printf("%lld")