正经题解 | 二进制高精度加法

包正经的好吧，不是那种写一大堆废话 直接把万能头内容粘贴过来 的代码，每一行（除了空行）都有自己的意义
代码使用string输入，再将string转换为二进制vector数组，使用二进制进行底层运算，再转为string输出
全篇仅用3个int类型，除此之外没有任何算术类型
因为用的是string输入输出，没有用算术类型存储，所以代码也可用于高精度A+B

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

class BinaryAdder
{
private:
    string convert(string dec)
    {
        string bin;
        while (dec != "0")
        {
            string rem = div2(dec);
            bin.push_back(rem[0]);
        }
        reverse(bin.begin(), bin.end());
        return bin.empty() ? "0" : bin;
    }

    string div2(string &num)
    {
        string quotient;
        char rem = '0';
        for (char c : num)
        {
            int current = (rem - '0') * 10 + (c - '0');
            quotient.push_back((current / 2) + '0');
            rem = (current % 2) + '0';
        }
        size_t start = quotient.find_first_not_of('0');
        if (start == string::npos)
            quotient = "0";
        else
            quotient = quotient.substr(start);
        num = quotient;
        return string(1, rem);
    }

    string badd(string bin1, string bin2)
    {
        reverse(bin1.begin(), bin1.end());
        reverse(bin2.begin(), bin2.end());
        string res;
        string carry = "0";

        size_t maxLen = max(bin1.size(), bin2.size());
        for (size_t i = 0; i < maxLen; i++)
        {
            string a = (i < bin1.size()) ? string(1, bin1[i]) : "0";
            string b = (i < bin2.size()) ? string(1, bin2[i]) : "0";
            string bitSum, newCarry;
            fadder(a, b, carry, bitSum, newCarry);
            res.push_back(bitSum[0]);
            carry = newCarry;
        }
        if (carry == "1")
            res.push_back('1');
        reverse(res.begin(), res.end());
        return res;
    }

    void fadder(string x, string y, string cin, string &sum, string &cout)
    {
        string xor1 = bxor(x, y);
        sum = bxor(xor1, cin);
        string and1 = band(x, y);
        string and2 = band(xor1, cin);
        cout = bor(and1, and2);
    }

    string bxor(string a, string b) { return (a != b) ? "1" : "0"; }
    string band(string a, string b) { return (a == "1" && b == "1") ? "1" : "0"; }
    string bor(string a, string b) { return (a == "1" || b == "1") ? "1" : "0"; }

    string bin2dec(string bin)
    {
        string dec = "0";
        string base = "1";
        reverse(bin.begin(), bin.end());
        for (char c : bin)
        {
            if (c == '1')
                dec = str_add(dec, base);
            base = str_mul2(base);
        }
        return dec;
    }

    string str_add(string a, string b)
    {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string ans;
        string carry = "0";
        size_t len = max(a.size(), b.size());
        for (size_t i = 0; i < len; i++)
        {
            char ca = (i < a.size()) ? a[i] : '0';
            char cb = (i < b.size()) ? b[i] : '0';
            int total = (ca - '0') + (cb - '0') + (carry[0] - '0');
            ans.push_back((total % 10) + '0');
            carry = (total >= 10) ? "1" : "0";
        }
        if (carry == "1")
            ans.push_back('1');
        reverse(ans.begin(), ans.end());
        return ans;
    }

    string str_mul2(string num)
    {
        reverse(num.begin(), num.end());
        string res;
        string carry = "0";
        for (char c : num)
        {
            int val = (c - '0') * 2 + (carry[0] - '0');
            res.push_back((val % 10) + '0');
            carry = (val >= 10) ? "1" : "0";
        }
        if (carry == "1")
            res.push_back('1');
        reverse(res.begin(), res.end());
        return res;
    }

public:
    string calculate(string s1, string s2)
    {
        string b1 = convert(s1);
        string b2 = convert(s2);
        string binResult = badd(b1, b2);
        return bin2dec(binResult);
    }
};

int main()
{
    BinaryAdder adder;
    string sa, sb;
    cin >> sa >> sb;
    string ans = adder.calculate(sa, sb);
    cout << ans << endl;
    return 0;
}