二进制高精度压位算法

Question

c++ 二进制+压位的+-*/%运算的高精度写法怎么写，乘法怎么优化，不用普通的乘法，位运算的

Answer 1

在C++中进行高精度的二进制加法、减法、乘法、除法和取模运算通常需要自己实现。以下是一些常见的高精度运算的示例代码以及一种位运算的优化方法：

1. 高精度加法：

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int>& a, vector<int>& b) {
    int carry = 0;
    vector<int> result;
    for (int i = 0; i < max(a.size(), b.size()) || carry; i++) {
        if (i == result.size()) result.push_back(0);
        int sum = result[i] + carry + (i < a.size() ? a[i] : 0) + (i < b.size() ? b[i] : 0);
        result[i] = sum % 2;
        carry = sum / 2;
    }
    return result;
}

1. 高精度减法：

vector<int> subtract(vector<int>& a, vector<int>& b) {
    int borrow = 0;
    vector<int> result;
    for (int i = 0; i < a.size(); i++) {
        int sub = a[i] - borrow - (i < b.size() ? b[i] : 0);
        if (sub < 0) {
            sub += 2;
            borrow = 1;
        } else {
            borrow = 0;
        }
        result.push_back(sub);
    }
    while (!result.empty() && result.back() == 0) result.pop_back();
    return result;
}

1. 高精度乘法（位运算优化）：

vector<int> multiply(vector<int>& a, vector<int>& b) {
    vector<int> result(a.size() + b.size(), 0);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            result[i + j] += a[i] * b[j];
            if (result[i + j] >= 2) {
                result[i + j + 1] += result[i + j] / 2;
                result[i + j] %= 2;
            }
        }
    }
    while (!result.empty() && result.back() == 0) result.pop_back();
    return result;
}

1. 高精度除法：

pair<vector<int>, int> divide(vector<int>& a, int b) {
    vector<int> result(a.size(), 0);
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        int dividend = carry * 2 + a[i];
        result[i] = dividend / b;
        carry = dividend % b;
    }
    while (!result.empty() && result.back() == 0) result.pop_back();
    return {result, carry};
}

1. 高精度取模：

int mod(vector<int>& a, int b) {
    int carry = 0;
    for (int i = 0; i < a.size(); i++) {
        int dividend = carry * 2 + a[i];
        carry = dividend % b;
    }
    return carry;
}