二进制高精度压位算法

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

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

高精度加法：

#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;
}

高精度减法：

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;
}

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

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;
}

高精度除法：

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};
}

高精度取模：

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;
}

【相关推荐】

你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/1089888
你也可以参考下这篇文章：【经典逆向思维】二进制转十进制从高位向低位转化
您还可以看一下刘磊老师的计算机进制转换课程中的二进制整数转为十进制数小节, 巩固相关知识点
除此之外, 这篇博客: 二进制运算中的 高级算法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
- 不断去除aaa最右边的比特111，直到a=0a=0a=0，其执行次数就是aaa包含的111的个数。
- 去除aaa最右边的比特111，根据结果是否为000，判断aaa是否是222的幂次。
- 将aaa的最右边的111串进位，并把最右边的111串的长度kkk计算出来，将k−1k-1k−1长的111串添加到最右边，得到恰好比aaa大的、包含同样多的111的下一个数。这就是组合。
- 有限域GF(2n)≅Z2[x]/m(x)GF(2^n) \cong Z_2[x]/m(x)GF(2n)≅Z2[x]/m(x)，将元素表示为{0,1}n\{0,1\}^n{0,1}n，且m(x)m(x)m(x)写作n+1n+1n+1长的二进制串
  - 加法：a⊕ba \oplus ba⊕b，按位异或
  - 乘法：令c=0nc=0^{n}c=0n，从右向左扫描bbb的每一位
    - 如果是bib_ibi是111，那么c←c⊕ac \leftarrow c \oplus ac←c⊕a
    - a←x⋅a(x)mod m(x)a \leftarrow x \cdot a(x) \mod m(x)a←x⋅a(x)modm(x)，先左移111位，再根据ana_nan决定是否异或
- 假设64比特数a,pa,pa,p，计算a′=amod pa' = a \mod pa′=amodp模约简结果在[−p/2,p/2)[-p/2,p/2)[−p/2,p/2)范围内，若要转换到[0,p)[0,p)[0,p)之间，只需计算a′+=(a′≫63)&pa' += (a' \gg 63) \& pa′+=(a′≫63)&p；若a′≥0a' \ge 0a′≥0，那么(a′≫63)=0x0000000000000000=0(a' \gg 63) = 0x0000000000000000 = 0(a′≫63)=0x0000000000000000=0；若a′<0a' < 0a′<0，那么(a′≫63)=0xFFFFFFFFFFFFFFFF=−1(a' \gg 63) = 0xFFFFFFFFFFFFFFFF = -1(a′≫63)=0xFFFFFFFFFFFFFFFF=−1

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^