高精度改为vector

include/bstl/big_integer.hpp

@@ -2,6 +2,7 @@
 #define BETTERSTL_BIG_INTEGER_HPP
 
 #include <string>
+#include <vector>
 #include <iostream>
 
 namespace bstl {
@@ -55,15 +56,15 @@ public:
     BigInteger operator/(const BigInteger& other) const;
 
 private:
-    std::string m_digits;  // 无符号数字，从高位到低位
+    std::vector<int> m_digits;  // 无符号数字，低位在前
     int m_sign;                 // -1, 0, 1
 
-    static std::string m_trimLeadingZeros(const std::string& value);
+    static std::vector<int> m_trimLeadingZeros(const std::vector<int>& value);
-    static int m_compareAbs(const std::string& a, const std::string& b);
+    static int m_compareAbs(const std::vector<int>& a, const std::vector<int>& b);
-    static std::string m_addAbs(const std::string& a, const std::string& b);
+    static std::vector<int> m_addAbs(const std::vector<int>& a, const std::vector<int>& b);
-    static std::string m_subAbs(const std::string& a, const std::string& b);
+    static std::vector<int> m_subAbs(const std::vector<int>& a, const std::vector<int>& b);
-    static std::string m_mulAbs(const std::string& a, const std::string& b);
+    static std::vector<int> m_mulAbs(const std::vector<int>& a, const std::vector<int>& b);
-    static std::string divAbs(const std::string& a, const std::string& b);
+    static std::vector<int> m_divAbs(const std::vector<int>& a, const std::vector<int>& b);
 };
 
 // 流运算符重载

src/big_integer.cpp

@@ -7,52 +7,81 @@
 
 namespace bstl {
 
-std::string BigInteger::m_trimLeadingZeros(const std::string& value) {
+namespace {
-    size_t pos = 0;
+std::vector<int> toDigits(unsigned long long value) {
-    while (pos < value.size() - 1 && value[pos] == '0') {
+    std::vector<int> digits;
-        pos++;
+    while (value > 0) {
+        digits.push_back(static_cast<int>(value % 10));
+        value /= 10;
     }
-    return value.substr(pos);
+    return digits;
 }
+}  // namespace
 
-int BigInteger::m_compareAbs(const std::string& a, const std::string& b) {
+std::vector<int> BigInteger::m_trimLeadingZeros(const std::vector<int>& value) {
-    std::string ta = m_trimLeadingZeros(a);
+    size_t end = value.size();
-    std::string tb = m_trimLeadingZeros(b);
+    while (end > 0 && value[end - 1] == 0) {
-    if (ta.size() != tb.size()) {
+        --end;
-        return ta.size() < tb.size() ? -1 : 1;
-    }
-    return ta.compare(tb) < 0 ? -1 : (ta.compare(tb) > 0 ? 1 : 0);
-}
-
-std::string BigInteger::m_addAbs(const std::string& a, const std::string& b) {
-    std::string result;
-    int carry = 0;
-    int i = static_cast<int>(a.size()) - 1;
-    int j = static_cast<int>(b.size()) - 1;
-    while (i >= 0 || j >= 0 || carry) {
-        int sum = carry;
-        if (i >= 0) sum += a[i--] - '0';
-        if (j >= 0) sum += b[j--] - '0';
-        result.insert(result.begin(), static_cast<char>('0' + sum % 10));
-        carry = sum / 10;
     }
+    std::vector<int> result(value);
+    result.resize(end);
     return result;
 }
 
-std::string BigInteger::m_subAbs(const std::string& a, const std::string& b) {
+int BigInteger::m_compareAbs(const std::vector<int>& a, const std::vector<int>& b) {
-    std::string ta = m_trimLeadingZeros(a);
+    std::vector<int> ta = m_trimLeadingZeros(a);
-    std::string tb = m_trimLeadingZeros(b);
+    std::vector<int> tb = m_trimLeadingZeros(b);
+    if (ta.size() != tb.size()) {
+        return ta.size() < tb.size() ? -1 : 1;
+    }
+    for (size_t i = ta.size(); i > 0; --i) {
+        if (ta[i - 1] != tb[i - 1]) {
+            return ta[i - 1] < tb[i - 1] ? -1 : 1;
+        }
+    }
+    return 0;
+}
+
+std::vector<int> BigInteger::m_addAbs(const std::vector<int>& a, const std::vector<int>& b) {
+    std::vector<int> ta = m_trimLeadingZeros(a);
+    std::vector<int> tb = m_trimLeadingZeros(b);
+    std::vector<int> result;
+    result.reserve(std::max(ta.size(), tb.size()) + 1);
+
+    int carry = 0;
+    const size_t n = std::max(ta.size(), tb.size());
+    for (size_t i = 0; i < n; ++i) {
+        int sum = carry;
+        if (i < ta.size()) {
+            sum += ta[i];
+        }
+        if (i < tb.size()) {
+            sum += tb[i];
+        }
+        result.push_back(sum % 10);
+        carry = sum / 10;
+    }
+    if (carry != 0) {
+        result.push_back(carry);
+    }
+    return m_trimLeadingZeros(result);
+}
+
+std::vector<int> BigInteger::m_subAbs(const std::vector<int>& a, const std::vector<int>& b) {
+    std::vector<int> ta = m_trimLeadingZeros(a);
+    std::vector<int> tb = m_trimLeadingZeros(b);
     if (m_compareAbs(ta, tb) < 0) {
         return m_subAbs(tb, ta);
     }
-    std::string result;
+
+    std::vector<int> result;
+    result.reserve(ta.size());
+
     int borrow = 0;
-    int i = static_cast<int>(ta.size()) - 1;
+    for (size_t i = 0; i < ta.size(); ++i) {
-    int j = static_cast<int>(tb.size()) - 1;
+        int diff = ta[i] - borrow;
-    while (i >= 0) {
+        if (i < tb.size()) {
-        int diff = (ta[i--] - '0') - borrow;
+            diff -= tb[i];
-        if (j >= 0) {
-            diff -= (tb[j--] - '0');
         }
         if (diff < 0) {
             diff += 10;
@@ -60,122 +89,113 @@ std::string BigInteger::m_subAbs(const std::string& a, const std::string& b) {
         } else {
             borrow = 0;
         }
-        result.insert(result.begin(), static_cast<char>('0' + diff));
+        result.push_back(diff);
     }
     return m_trimLeadingZeros(result);
 }
 
-std::string BigInteger::m_mulAbs(const std::string& a, const std::string& b) {
+std::vector<int> BigInteger::m_mulAbs(const std::vector<int>& a, const std::vector<int>& b) {
-    std::string ta = m_trimLeadingZeros(a);
+    std::vector<int> ta = m_trimLeadingZeros(a);
-    std::string tb = m_trimLeadingZeros(b);
+    std::vector<int> tb = m_trimLeadingZeros(b);
-    if (ta == "0" || tb == "0") return "0";
+    if (ta.empty() || tb.empty()) {
+        return {};
+    }
 
     std::vector<int> product(ta.size() + tb.size(), 0);
-    for (size_t i = 0; i < ta.size(); i++) {
+    for (size_t i = 0; i < ta.size(); ++i) {
-        for (size_t j = 0; j < tb.size(); j++) {
+        for (size_t j = 0; j < tb.size(); ++j) {
-            int mul = (ta[ta.size() - 1 - i] - '0') * (tb[tb.size() - 1 - j] - '0');
+            product[i + j] += ta[i] * tb[j];
-            product[i + j] += mul;
         }
     }
 
     int carry = 0;
-    for (int & i : product) {
+    for (int& digit : product) {
-        int sum = i + carry;
+        const int sum = digit + carry;
-        i = sum % 10;
+        digit = sum % 10;
         carry = sum / 10;
     }
 
-    std::string result;
+    return m_trimLeadingZeros(product);
-    for (int i = static_cast<int>(product.size()) - 1; i >= 0; i--) {
-        result += char('0' + product[i]);
-    }
-    return m_trimLeadingZeros(result);
 }
 
-std::string BigInteger::divAbs(const std::string& a, const std::string& b) {
+std::vector<int> BigInteger::m_divAbs(const std::vector<int>& a, const std::vector<int>& b) {
-    std::string tb = m_trimLeadingZeros(b);
+    std::vector<int> tb = m_trimLeadingZeros(b);
-    if (tb == "0") {
+    if (tb.empty()) {
         throw std::invalid_argument("division by zero");
     }
-    std::string ta = m_trimLeadingZeros(a);
+
+    std::vector<int> ta = m_trimLeadingZeros(a);
     if (m_compareAbs(ta, tb) < 0) {
-        return "0";
+        return {};
     }
 
-    std::string quotient;
+    std::vector<int> quotientHigh;
-    std::string current;
+    std::vector<int> current;
-    for (char digit : ta) {
+    current.reserve(ta.size());
-        current += digit;
+
+    for (size_t i = ta.size(); i > 0; --i) {
+        current.insert(current.begin(), ta[i - 1]);
         current = m_trimLeadingZeros(current);
         int count = 0;
         while (m_compareAbs(current, tb) >= 0) {
             current = m_subAbs(current, tb);
-            count++;
+            ++count;
         }
-        quotient += char('0' + count);
+        quotientHigh.push_back(count);
-    }
-    return m_trimLeadingZeros(quotient);
     }
 
-BigInteger::BigInteger() : m_digits("0"), m_sign(0) {}
+    std::reverse(quotientHigh.begin(), quotientHigh.end());
+    return m_trimLeadingZeros(quotientHigh);
+}
 
-BigInteger::BigInteger(int value) : m_digits("0"), m_sign(1) {
+BigInteger::BigInteger() : m_sign(0) {}
+
+BigInteger::BigInteger(int value) : m_sign(0) {
     if (value == 0) {
-        m_digits = "0";
-        m_sign = 0;
         return;
     }
+
+    auto v = static_cast<long long>(value);
+    if (v < 0) {
+        m_sign = -1;
+        v = -v;
+    } else {
+        m_sign = 1;
+    }
+    m_digits = toDigits(static_cast<unsigned long long>(v));
+}
+
+BigInteger::BigInteger(long long value) : m_sign(0) {
+    if (value == 0) {
+        return;
+    }
+
+    unsigned long long magnitude = 0;
     if (value < 0) {
         m_sign = -1;
-        value = -value;
+        magnitude = static_cast<unsigned long long>(-(value + 1)) + 1ULL;
-    }
+    } else {
-    m_digits.clear();
+        m_sign = 1;
-    while (value > 0) {
+        magnitude = static_cast<unsigned long long>(value);
-        m_digits = char('0' + value % 10) + m_digits;
-        value /= 10;
     }
+    m_digits = toDigits(magnitude);
 }
 
-BigInteger::BigInteger(long long value) : m_digits("0"), m_sign(1) {
+BigInteger::BigInteger(unsigned long long value) : m_sign(0) {
     if (value == 0) {
-        m_digits = "0";
-        m_sign = 0;
         return;
     }
-    if (value < 0) {
+    m_sign = 1;
-        m_sign = -1;
+    m_digits = toDigits(value);
-        value = -value;
-    }
-    m_digits.clear();
-    while (value > 0) {
-        m_digits = char('0' + value % 10) + m_digits;
-        value /= 10;
-    }
 }
 
-BigInteger::BigInteger(unsigned long long value) : m_digits("0"), m_sign(1) {
+BigInteger::BigInteger(const std::string& value) : m_sign(0) {
-    if (value == 0) {
-        m_digits = "0";
-        m_sign = 0;
-        return;
-    }
-    m_digits.clear();
-    while (value > 0) {
-        m_digits = char('0' + value % 10) + m_digits;
-        value /= 10;
-    }
-}
-
-BigInteger::BigInteger(const std::string& value) : m_digits("0"), m_sign(1) {
     if (value.empty()) {
-        m_digits = "0";
-        m_sign = 0;
         return;
     }
 
     std::string text = value;
     m_sign = 1;
-
     if (text[0] == '-') {
         m_sign = -1;
         text = text.substr(1);
@@ -184,7 +204,6 @@ BigInteger::BigInteger(const std::string& value) : m_digits("0"), m_sign(1) {
     }
 
     if (text.empty()) {
-        m_digits = "0";
         m_sign = 0;
         return;
     }
@@ -195,8 +214,13 @@ BigInteger::BigInteger(const std::string& value) : m_digits("0"), m_sign(1) {
         }
     }
 
-    m_digits = m_trimLeadingZeros(text);
+    m_digits.clear();
-    if (m_digits == "0") {
+    m_digits.reserve(text.size());
+    for (auto it = text.rbegin(); it != text.rend(); ++it) {
+        m_digits.push_back(*it - '0');
+    }
+    m_digits = m_trimLeadingZeros(m_digits);
+    if (m_digits.empty()) {
         m_sign = 0;
     }
 }
@@ -205,20 +229,33 @@ BigInteger::BigInteger(const char* value)
     : BigInteger(value == nullptr ? std::string("0") : std::string(value)) {}
 
 bool BigInteger::isZero() const {
-    return m_sign == 0 || m_digits == "0";
+    return m_sign == 0;
 }
 
 int BigInteger::sign() const {
-    return isZero() ? 0 : m_sign;
+    return m_sign;
 }
 
 std::string BigInteger::toString() const {
-    if (isZero()) return "0";
+    if (isZero()) {
-    return (m_sign < 0 ? "-" : "") + m_digits;
+        return "0";
+    }
+
+    std::string result;
+    result.reserve(m_digits.size() + (m_sign < 0 ? 1U : 0U));
+    if (m_sign < 0) {
+        result.push_back('-');
+    }
+    for (auto it = m_digits.rbegin(); it != m_digits.rend(); ++it) {
+        result.push_back(static_cast<char>('0' + *it));
+    }
+    return result;
 }
 
 bool BigInteger::operator==(const BigInteger& other) const {
-    if (isZero() && other.isZero()) return true;
+    if (isZero() && other.isZero()) {
+        return true;
+    }
     return m_sign == other.m_sign && m_digits == other.m_digits;
 }
 
@@ -227,9 +264,13 @@ bool BigInteger::operator!=(const BigInteger& other) const {
 }
 
 bool BigInteger::operator<(const BigInteger& other) const {
-    if (m_sign != other.m_sign) return m_sign < other.m_sign;
+    if (m_sign != other.m_sign) {
-    if (m_sign == 0) return false;
+        return m_sign < other.m_sign;
-    int cmp = m_compareAbs(m_digits, other.m_digits);
+    }
+    if (m_sign == 0) {
+        return false;
+    }
+    const int cmp = m_compareAbs(m_digits, other.m_digits);
     return m_sign > 0 ? cmp < 0 : cmp > 0;
 }
 
@@ -298,7 +339,9 @@ BigInteger BigInteger::operator+() const {
 }
 
 BigInteger BigInteger::operator-() const {
-    if (isZero()) return {0};
+    if (isZero()) {
+        return {0};
+    }
     BigInteger result(*this);
     result.m_sign = -result.m_sign;
     return result;
@@ -325,17 +368,21 @@ BigInteger& BigInteger::operator/=(const BigInteger& other) {
 }
 
 BigInteger BigInteger::operator+(const BigInteger& other) const {
-    if (isZero()) return other;
+    if (isZero()) {
-    if (other.isZero()) return *this;
+        return other;
+    }
+    if (other.isZero()) {
+        return *this;
+    }
 
     BigInteger result;
     if (m_sign == other.m_sign) {
         result.m_digits = m_addAbs(m_digits, other.m_digits);
         result.m_sign = m_sign;
     } else {
-        int cmp = m_compareAbs(m_digits, other.m_digits);
+        const int cmp = m_compareAbs(m_digits, other.m_digits);
         if (cmp == 0) {
-            result.m_digits = "0";
+            result.m_digits.clear();
             result.m_sign = 0;
         } else if (cmp > 0) {
             result.m_digits = m_subAbs(m_digits, other.m_digits);
@@ -345,7 +392,9 @@ BigInteger BigInteger::operator+(const BigInteger& other) const {
             result.m_sign = other.m_sign;
         }
     }
-    if (result.m_digits == "0") result.m_sign = 0;
+    if (result.m_digits.empty()) {
+        result.m_sign = 0;
+    }
     return result;
 }
 
@@ -354,11 +403,16 @@ BigInteger BigInteger::operator-(const BigInteger& other) const {
 }
 
 BigInteger BigInteger::operator*(const BigInteger& other) const {
-    if (isZero() || other.isZero()) return {0};
+    if (isZero() || other.isZero()) {
+        return {0};
+    }
+
     BigInteger result;
     result.m_digits = m_mulAbs(m_digits, other.m_digits);
-    result.m_sign = (m_sign * other.m_sign);
+    result.m_sign = m_sign * other.m_sign;
-    if (result.m_digits == "0") result.m_sign = 0;
+    if (result.m_digits.empty()) {
+        result.m_sign = 0;
+    }
     return result;
 }
 
@@ -366,11 +420,16 @@ BigInteger BigInteger::operator/(const BigInteger& other) const {
     if (other.isZero()) {
         throw std::invalid_argument("division by zero");
     }
-    if (isZero()) return {0};
+    if (isZero()) {
+        return {0};
+    }
+
     BigInteger result;
-    result.m_digits = divAbs(m_digits, other.m_digits);
+    result.m_digits = m_divAbs(m_digits, other.m_digits);
-    result.m_sign = (m_sign * other.m_sign);
+    result.m_sign = m_sign * other.m_sign;
-    if (result.m_digits == "0") result.m_sign = 0;
+    if (result.m_digits.empty()) {
+        result.m_sign = 0;
+    }
     return result;
 }
 
@@ -386,4 +445,3 @@ std::istream& operator>>(std::istream& is, BigInteger& bi) {
 }
 
 }  // namespace bstl
-