专栏文章

高精度优化

wwenzhenhao
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip1p9qb
此快照首次捕获于
2025/12/03 04:43
3 个月前
此快照最后确认于
2025/12/03 04:43
3 个月前
查看原文

引入

众所周知，高精度是一个十分耗内存的东西。我们要通过用 int 或 short 数组来储存每一位数字。
然而，short 能表示的范围是 65,535(216)65,535 (2^{16}) 。这无疑增加了空间复杂度。比如说表示 10241024 。它是一个 44 位数。按照每位占 1616 位 bit 位算，一共需要 4×16=644×16=64 个 bit 位。然而 1024=2101024=2^{10} ，实际上只需要 1010 bit 位储存即可。让我们计算一下，存在了 66 倍的差距。即使更换成更大的数据，它的倍数关系也稳定于 44 到 66 倍。这无疑是一种浪费。
就没有别的办法了吗？

准备工作

在解决问题之前，我们不得不准备一些东西。
是的，用 short 来储存十进制的数位显然是行不通的。那么，我们可以尝试用 bool 数组进行储存。此处示例使用 vector<bool>。
我们可以用泛型模板类的形式封装数字，并重载各种运算符，达到高精度的效果。
在此之前还需声明一下，所谓鱼和熊掌不可兼得。当你的数据范围增大时，使用 22 进制数组的效率明显比 1010 进制的数组低得多。因此不推荐在赛场上使用。
此处用到以下头文件：
CPP
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdexcept>//当然你也可以使用万能头

逐步完成

一个好框架

既然是模板类，一个好的框架是必不可少的。下面是该类的框架，_value 是该数字的 bit 位数量。
CPP
template<size_t _value>
class BigNum {
    //________
};

private 部分 变量定义&辅助函数

首先是变量，实际上不需要太多，仅仅需要储存一个 bool 数组即可。
CPP
vector<bool>bits;// 二进制位，bits[0]为最低位，bits[_value-1]为最高位
接下来是 22 个辅助函数，用于进制转换。
CPP
// 辅助函数：十进制字符串转换为二进制
void fromDecimalString(const string& decStr) {
    string current = decStr;
    size_t pos = 0;

    // 去除前导空格
    size_t start = current.find_first_not_of(' ');
    if (start != string::npos) {
        current = current.substr(start);
    }

    // 检查有效数字
    if (current.empty() || 
        current.find_first_not_of("0123456789") != string::npos) {
        throw invalid_argument("Invalid decimal string");
    }

    // 去除前导0
    size_t nonZeroPos = current.find_first_not_of('0');
    if (nonZeroPos == string::npos) {
        fill(bits.begin(), bits.end(), false); // 全0
        return;
    }
    current = current.substr(nonZeroPos);

    // 模拟除2过程
    while (!current.empty() && pos < _value) {
        int remainder = 0;
        string next;
        for (char c : current) {
            int digit = c - '0';
            int num = remainder * 10 + digit;
            int quot = num / 2;
            remainder = num % 2;
            if (!next.empty() || quot != 0) {
                next.push_back(quot + '0');
            }
        }
        bits[pos++] = (remainder == 1);
        current = next;
    }
}

// 辅助函数：二进制转十进制字符串
string toDecimalString() const {
    string result = "0";
    // 从最高位开始处理
    for (int i = static_cast<int>(_value) - 1; i >= 0; i--) {
        // 乘以2
        int carry = 0;
        for (int j = result.size() - 1; j >= 0; j--) {
            int digit = result[j] - '0';
            int temp = digit * 2 + carry;
            carry = temp / 10;
            result[j] = (temp % 10) + '0';
        }
        if (carry > 0) {
            result.insert(result.begin(), carry + '0');
        }
        // 加当前位
        if (bits[i]) {
            int carryAdd = 1;
            for (int j = result.size() - 1; j >= 0 && carryAdd > 0; j--) {
                int digit = result[j] - '0';
                int sum = digit + carryAdd;
                carryAdd = sum / 10;
                result[j] = (sum % 10) + '0';
            }
            if (carryAdd > 0) {
                result.insert(result.begin(), carryAdd + '0');
            }
        }
    }
    // 去除前导0
    size_t nonZero = result.find_first_not_of('0');
    if (nonZero == string::npos) return "0";
    return result.substr(nonZero);
}
由于我们要表示高精度，所以对转换的十进制以 string 字符串的形式保存。

public 部分

接下来就是一些公开函数。包括构造、重载与友元。

构造函数

构造函数的主要任务是初始化，下面展示了初始为 00 、字符串 string 初始化和用 BigNum 类初始化的构造函数。
CPP
// 构造函数
BigNum() : bits(_value, false) {}
explicit BigNum(const string& decStr) : bits(_value, false) {
    fromDecimalString(decStr);
}
BigNum(const BigNum& other) : bits(other.bits) {}

赋值

这是最基本的重载，只需要对 bits 进行复制即可。由于这里使用的是 vector ，所以可以直接赋值。如果你用的是数组，那就需要循环了。
CPP
BigNum& operator=(const BigNum& other) {
    if (this != &other) {
        bits = other.bits;
    }
    return *this;
}

位运算

位运算也算简单，对每一 bit 位进行一一比较即可。
CPP
BigNum operator&(const BigNum& other) const {
    BigNum result;
    for (size_t i = 0; i < _value; i++) {
        result.bits[i] = bits[i] & other.bits[i];
    }
    return result;
}

BigNum operator|(const BigNum& other) const {
    BigNum result;
    for (size_t i = 0; i < _value; i++) {
        result.bits[i] = bits[i] | other.bits[i];
    }
    return result;
}

BigNum operator^(const BigNum& other) const {
    BigNum result;
    for (size_t i = 0; i < _value; i++) {
        result.bits[i] = bits[i] ^ other.bits[i];
    }
    return result;
}

BigNum operator~() const {
    BigNum result;
    for (size_t i = 0; i < _value; i++) {
        result.bits[i] = !bits[i];
    }
    return result;
}

BigNum operator<<(size_t shift) const {
    BigNum result;
    for (size_t i = 0; i < _value; i++) {
        if (i >= shift && i - shift < _value) {
            result.bits[i] = bits[i - shift];
        }
    }
    return result;
}

BigNum operator>>(size_t shift) const {
    BigNum result;
    for (int i = _value - 1; i >= 0; i--) {
        if (i + shift < _value) {
            result.bits[i] = bits[i + shift];
        }
    }
    return result;
}

算术运算

算术运算算是比较难的一部分，需要在草稿纸上模拟几遍才能得出规律。由于篇幅限制，这里仅展示 +−×+ - \times 运算。
CPP
BigNum operator+(const BigNum& other) const {
    BigNum result;
    bool carry = false;
    for (size_t i = 0; i < _value; i++) {
        bool a = bits[i];
        bool b = other.bits[i];
        result.bits[i] = a ^ b ^ carry;
        carry = (a && b) || (a && carry) || (b && carry);
    }
    return result;
}

BigNum operator-(const BigNum& other) const {
    BigNum result;
    bool borrow = false;
    for (size_t i = 0; i < _value; i++) {
        int a = bits[i] ? 1 : 0;
        int b = other.bits[i] ? 1 : 0;
        int total = a - b - (borrow ? 1 : 0);
        if (total < 0) {
            total += 2;
            borrow = true;
        } else {
            borrow = false;
        }
        result.bits[i] = total & 1;
    }
    return result;
}

BigNum operator*(const BigNum& other) const {
    BigNum result;
    for (size_t i = 0; i < _value; i++) {
        if (other.bits[i]) {
            BigNum temp = *this << i;
            result = result + temp;
        }
    }
    return result;
}

比较运算

类似于位运算，也是一一比较即可。
CPP
bool operator==(const BigNum& other) const {
    for (size_t i = 0; i < _value; i++) {
        if (bits[i] != other.bits[i]) {
            return false;
        }
    }
    return true;
}

bool operator!=(const BigNum& other) const {
    return !(*this == other);
}

bool operator<(const BigNum& other) const {
    for (int i = _value - 1; i >= 0; i--) {
        if (bits[i] < other.bits[i]) return true;
        if (bits[i] > other.bits[i]) return false;
    }
    return false;
}

bool operator<=(const BigNum& other) const {
    return (*this < other) || (*this == other);
}

bool operator>(const BigNum& other) const {
    return !(*this <= other);
}

友元函数

友元函数我们用于重载 cin 和 cout 。也就是说，我们要重载 ostream 和 istream ，这样也便于文件读写。
CPP
friend ostream& operator<<(ostream& os, const BigNum& num) {
    os << num.toDecimalString();
    return os;
}

friend istream& operator>>(istream& is, BigNum& num) {
    string s;
    is >> s;
    num = BigNum(s);
    return is;
}

完整代码

这里我们通过 sort 排序来检验这个类的可靠性。
CPP
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdexcept>
using namespace std;

template <size_t _value>
class BigNum {
private:
    vector<bool> bits; // 二进制位，bits[0]为最低位，bits[_value-1]为最高位

    // 辅助函数：十进制字符串转换为二进制
    void fromDecimalString(const string& decStr) {
        string current = decStr;
        size_t pos = 0;

        // 去除前导空格
        size_t start = current.find_first_not_of(' ');
        if (start != string::npos) {
            current = current.substr(start);
        }

        // 检查有效数字
        if (current.empty() || 
            current.find_first_not_of("0123456789") != string::npos) {
            throw invalid_argument("Invalid decimal string");
        }

        // 去除前导0
        size_t nonZeroPos = current.find_first_not_of('0');
        if (nonZeroPos == string::npos) {
            fill(bits.begin(), bits.end(), false); // 全0
            return;
        }
        current = current.substr(nonZeroPos);

        // 模拟除2过程
        while (!current.empty() && pos < _value) {
            int remainder = 0;
            string next;
            for (char c : current) {
                int digit = c - '0';
                int num = remainder * 10 + digit;
                int quot = num / 2;
                remainder = num % 2;
                if (!next.empty() || quot != 0) {
                    next.push_back(quot + '0');
                }
            }
            bits[pos++] = (remainder == 1);
            current = next;
        }
    }

    // 辅助函数：二进制转十进制字符串
    string toDecimalString() const {
        string result = "0";
        // 从最高位开始处理
        for (int i = static_cast<int>(_value) - 1; i >= 0; i--) {
            // 乘以2
            int carry = 0;
            for (int j = result.size() - 1; j >= 0; j--) {
                int digit = result[j] - '0';
                int temp = digit * 2 + carry;
                carry = temp / 10;
                result[j] = (temp % 10) + '0';
            }
            if (carry > 0) {
                result.insert(result.begin(), carry + '0');
            }
            // 加当前位
            if (bits[i]) {
                int carryAdd = 1;
                for (int j = result.size() - 1; j >= 0 && carryAdd > 0; j--) {
                    int digit = result[j] - '0';
                    int sum = digit + carryAdd;
                    carryAdd = sum / 10;
                    result[j] = (sum % 10) + '0';
                }
                if (carryAdd > 0) {
                    result.insert(result.begin(), carryAdd + '0');
                }
            }
        }
        // 去除前导0
        size_t nonZero = result.find_first_not_of('0');
        if (nonZero == string::npos) return "0";
        return result.substr(nonZero);
    }

public:
    // 构造函数
    BigNum() : bits(_value, false) {}
    explicit BigNum(const string& decStr) : bits(_value, false) {
        fromDecimalString(decStr);
    }
    BigNum(const BigNum& other) : bits(other.bits) {}

    // 赋值运算符
    BigNum& operator=(const BigNum& other) {
        if (this != &other) {
            bits = other.bits;
        }
        return *this;
    }

    // 转换为十进制字符串
    string toString() const {
        return toDecimalString();
    }

    // 位运算
    BigNum operator&(const BigNum& other) const {
        BigNum result;
        for (size_t i = 0; i < _value; i++) {
            result.bits[i] = bits[i] & other.bits[i];
        }
        return result;
    }

    BigNum operator|(const BigNum& other) const {
        BigNum result;
        for (size_t i = 0; i < _value; i++) {
            result.bits[i] = bits[i] | other.bits[i];
        }
        return result;
    }

    BigNum operator^(const BigNum& other) const {
        BigNum result;
        for (size_t i = 0; i < _value; i++) {
            result.bits[i] = bits[i] ^ other.bits[i];
        }
        return result;
    }

    BigNum operator~() const {
        BigNum result;
        for (size_t i = 0; i < _value; i++) {
            result.bits[i] = !bits[i];
        }
        return result;
    }

    // 移位运算
    BigNum operator<<(size_t shift) const {
        BigNum result;
        for (size_t i = 0; i < _value; i++) {
            if (i >= shift && i - shift < _value) {
                result.bits[i] = bits[i - shift];
            }
        }
        return result;
    }

    BigNum operator>>(size_t shift) const {
        BigNum result;
        for (int i = _value - 1; i >= 0; i--) {
            if (i + shift < _value) {
                result.bits[i] = bits[i + shift];
            }
        }
        return result;
    }

    // 算术运算
    BigNum operator+(const BigNum& other) const {
        BigNum result;
        bool carry = false;
        for (size_t i = 0; i < _value; i++) {
            bool a = bits[i];
            bool b = other.bits[i];
            result.bits[i] = a ^ b ^ carry;
            carry = (a && b) || (a && carry) || (b && carry);
        }
        return result;
    }

    BigNum operator-(const BigNum& other) const {
        BigNum result;
        bool borrow = false;
        for (size_t i = 0; i < _value; i++) {
            int a = bits[i] ? 1 : 0;
            int b = other.bits[i] ? 1 : 0;
            int total = a - b - (borrow ? 1 : 0);
            if (total < 0) {
                total += 2;
                borrow = true;
            } else {
                borrow = false;
            }
            result.bits[i] = total & 1;
        }
        return result;
    }

    BigNum operator*(const BigNum& other) const {
        BigNum result;
        for (size_t i = 0; i < _value; i++) {
            if (other.bits[i]) {
                BigNum temp = *this << i;
                result = result + temp;
            }
        }
        return result;
    }

    // 比较运算符
    bool operator==(const BigNum& other) const {
        for (size_t i = 0; i < _value; i++) {
            if (bits[i] != other.bits[i]) {
                return false;
            }
        }
        return true;
    }

    bool operator!=(const BigNum& other) const {
        return !(*this == other);
    }

    bool operator<(const BigNum& other) const {
        for (int i = _value - 1; i >= 0; i--) {
            if (bits[i] < other.bits[i]) return true;
            if (bits[i] > other.bits[i]) return false;
        }
        return false;
    }

    bool operator<=(const BigNum& other) const {
        return (*this < other) || (*this == other);
    }

    bool operator>(const BigNum& other) const {
        return !(*this <= other);
    }

    bool operator>=(const BigNum& other) const {
        return !(*this < other);
    }

    // 输入输出流重载
    friend ostream& operator<<(ostream& os, const BigNum& num) {
        os << num.toDecimalString();
        return os;
    }

    friend istream& operator>>(istream& is, BigNum& num) {
        string s;
        is >> s;
        num = BigNum(s);
        return is;
    }
};
int main() {
	int n;
	cin >> n;
    BigNum<64> a[n+1];
    for(int i = 1;i <=n;i++)
    	cin>>a[i];
    sort(a + 1,a + n + 1);
    for(int i = 1;i <=n;i++)
    	cout<<a[i]<<" ";
    return 0;
}

尾声

这篇文章的主要目的是为了让大家深刻了解高精度转二进制这种优化办法，希望对大家有帮助。别忘了 c++11!

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...