如何将大数二进制形式存入u32int_t数组以实现高精度计算？

Got it, let's break down how to build this high-precision calculator using 32-bit blocks as requested. I'll walk through each key part with code examples using only standard C++ libraries.

1. 核心数据结构设计 #

First, we'll use a class to encapsulate our big number. The core storage is a std::vector<uint32_t> where each element holds a 32-bit chunk of the number, stored in little-endian order (lowest bits first). This makes carry/borrow operations way easier since we start calculations from the least significant chunk.

#include <cstdint>
#include <vector>
#include <string>
#include <algorithm>
#include <stdexcept>
#include <iostream>

class BigNumber {
private:
    std::vector<uint32_t> blocks;  // 32-bit chunks, lowest bits first
    bool is_negative = false;      // Track negative numbers

    // Helper: Remove leading zero chunks (since we use little-endian, these are at the end)
    void trim_leading_zeros() {
        while (blocks.size() > 1 && blocks.back() == 0) {
            blocks.pop_back();
        }
        if (blocks.size() == 1 && blocks[0] == 0) {
            is_negative = false;  // Zero is never negative
        }
    }

    // Helper: Compare absolute values of two BigNumbers
    int compare_abs(const BigNumber& other) const {
        if (blocks.size() != other.blocks.size()) {
            return blocks.size() > other.blocks.size() ? 1 : -1;
        }
        // Compare from highest chunk to lowest
        for (int i = blocks.size() - 1; i >= 0; --i) {
            if (blocks[i] != other.blocks[i]) {
                return blocks[i] > other.blocks[i] ? 1 : -1;
            }
        }
        return 0;  // Equal
    }

    // Helper: Check if the number is zero
    bool is_zero() const {
        return blocks.size() == 1 && blocks[0] == 0;
    }

public:
    // Default constructor (zero)
    BigNumber() : blocks({0}) {}

    // Constructor from string input
    BigNumber(const std::string& num_str);

    // Arithmetic operators
    BigNumber operator+(const BigNumber& other) const;
    BigNumber operator-(const BigNumber& other) const;
    BigNumber operator*(const BigNumber& other) const;
    BigNumber operator/(const BigNumber& other) const;

    // Convert back to string for output
    std::string to_string() const;
};

2. String to 32-bit Block Conversion #

Next, we need to convert the input string (decimal) into our 32-bit chunk array. The logic here is repeatedly dividing the decimal string by 2^32 to get each chunk, then keeping the quotient as the new string to process.

BigNumber::BigNumber(const std::string& num_str) {
    // Handle sign
    size_t start_idx = 0;
    if (!num_str.empty() && num_str[0] == '-') {
        is_negative = true;
        start_idx = 1;
    } else if (!num_str.empty() && num_str[0] == '+') {
        start_idx = 1;
    }

    // Handle empty input or zero
    if (start_idx >= num_str.size() || num_str.substr(start_idx) == "0") {
        blocks.push_back(0);
        is_negative = false;
        return;
    }

    std::string remaining = num_str.substr(start_idx);
    while (!remaining.empty()) {
        uint64_t current = 0;
        std::string new_remaining;

        // Process each digit to compute current chunk (mod 2^32) and new quotient
        for (char c : remaining) {
            uint64_t digit = c - '0';
            current = current * 10 + digit;
            if (current >= UINT32_MAX + 1ULL) {
                new_remaining += (current / (UINT32_MAX + 1ULL)) + '0';
                current %= (UINT32_MAX + 1ULL);
            } else if (!new_remaining.empty()) {
                new_remaining += '0';
            }
        }

        // Add the current chunk (only if non-zero or we already have chunks)
        if (current != 0 || !blocks.empty()) {
            blocks.push_back(static_cast<uint32_t>(current));
        }

        // Update remaining to the quotient, break if it's zero
        remaining = new_remaining.empty() ? "" : new_remaining;
        if (remaining == "0") break;
    }

    trim_leading_zeros();
}

3. Addition Operation #

Addition needs to handle same-sign and different-sign cases. For same signs, we add chunks directly with carry. For different signs, we convert it to a subtraction problem.

BigNumber BigNumber::operator+(const BigNumber& other) const {
    if (is_negative == other.is_negative) {
        // Same sign: add absolute values, keep sign
        BigNumber result;
        result.is_negative = is_negative;
        result.blocks.clear();
        uint64_t carry = 0;
        size_t max_size = std::max(blocks.size(), other.blocks.size());

        for (size_t i = 0; i < max_size || carry != 0; ++i) {
            uint64_t a = i < blocks.size() ? blocks[i] : 0;
            uint64_t b = i < other.blocks.size() ? other.blocks[i] : 0;
            uint64_t sum = a + b + carry;
            result.blocks.push_back(static_cast<uint32_t>(sum & 0xFFFFFFFFULL));
            carry = sum >> 32;
        }

        result.trim_leading_zeros();
        return result;
    } else {
        // Different signs: convert to subtraction
        if (is_negative) {
            BigNumber temp = *this;
            temp.is_negative = false;
            return other - temp;
        } else {
            BigNumber temp = other;
            temp.is_negative = false;
            return *this - temp;
        }
    }
}

4. Subtraction Operation #

Subtraction works similarly: handle same signs by comparing absolute values, and different signs by converting to addition. We also need to handle borrows when chunks are too small.

BigNumber BigNumber::operator-(const BigNumber& other) const {
    if (is_negative != other.is_negative) {
        // Different signs: convert to addition
        BigNumber temp = other;
        temp.is_negative = !temp.is_negative;
        return *this + temp;
    } else {
        // Same signs: compare absolute values first
        int cmp = compare_abs(other);
        if (cmp < 0) {
            // Other number is larger: reverse subtraction and flip sign
            BigNumber result = other - *this;
            result.is_negative = !is_negative;
            return result;
        } else if (cmp == 0) {
            // Equal numbers: result is zero
            return BigNumber("0");
        }

        // Current number is larger: perform subtraction with borrow
        BigNumber result;
        result.is_negative = is_negative;
        result.blocks.clear();
        uint64_t borrow = 0;

        for (size_t i = 0; i < blocks.size(); ++i) {
            uint64_t a = blocks[i];
            uint64_t b = i < other.blocks.size() ? other.blocks[i] : 0;
            uint64_t sub = a - b - borrow;

            if (a < b + borrow) {
                sub += 0x100000000ULL;
                borrow = 1;
            } else {
                borrow = 0;
            }

            result.blocks.push_back(static_cast<uint32_t>(sub));
        }

        result.trim_leading_zeros();
        return result;
    }
}

5. Multiplication Operation #

Multiplication uses a "long multiplication" approach with chunks. We multiply each chunk of the first number with each chunk of the second, accumulate the results in the correct position, and handle carry.

BigNumber BigNumber::operator*(const BigNumber& other) const {
    BigNumber result;
    result.blocks.resize(blocks.size() + other.blocks.size(), 0);
    result.is_negative = is_negative != other.is_negative;

    for (size_t i = 0; i < blocks.size(); ++i) {
        uint64_t carry = 0;
        for (size_t j = 0; j < other.blocks.size() || carry != 0; ++j) {
            uint64_t b = j < other.blocks.size() ? other.blocks[j] : 0;
            uint64_t product = static_cast<uint64_t>(blocks[i]) * b + result.blocks[i + j] + carry;
            result.blocks[i + j] = static_cast<uint32_t>(product & 0xFFFFFFFFULL);
            carry = product >> 32;
        }
    }

    result.trim_leading_zeros();
    return result;
}

6. Division Operation #

Division is trickier—we use a trial division approach. First, we handle signs and edge cases, then perform division on absolute values by repeatedly finding the largest multiple of the divisor that fits into the current portion of the dividend.

BigNumber BigNumber::operator/(const BigNumber& other) const {
    if (other.is_zero()) {
        throw std::invalid_argument("Division by zero is not allowed");
    }
    if (this->is_zero()) {
        return BigNumber("0");
    }

    // Work with absolute values
    BigNumber dividend = *this;
    dividend.is_negative = false;
    BigNumber divisor = other;
    divisor.is_negative = false;

    BigNumber quotient;
    quotient.blocks.resize(dividend.blocks.size(), 0);
    BigNumber current;

    // Process from highest chunk to lowest
    for (int i = dividend.blocks.size() - 1; i >= 0; --i) {
        // Shift current left by 32 bits and add the next chunk
        current.blocks.insert(current.blocks.begin(), dividend.blocks[i]);
        current.trim_leading_zeros();

        // Binary search for the largest k where divisor * k <= current
        uint32_t k = 0;
        uint32_t low = 0, high = 0xFFFFFFFF;
        while (low <= high) {
            uint32_t mid = low + (high - low) / 2;
            BigNumber temp = divisor * BigNumber(std::to_string(mid));
            if (temp.compare_abs(current) <= 0) {
                k = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        quotient.blocks[i] = k;
        current = current - divisor * BigNumber(std::to_string(k));
    }

    quotient.is_negative = is_negative != other.is_negative;
    quotient.trim_leading_zeros();
    return quotient;
}

7. Convert Back to String #

To verify results, we need to convert our 32-bit chunks back to a decimal string. We do this by repeatedly dividing the number by 10 and collecting remainders.

std::string BigNumber::to_string() const {
    if (is_zero()) {
        return "0";
    }

    std::string result;
    BigNumber temp = *this;
    temp.is_negative = false;

    while (!temp.is_zero()) {
        uint64_t remainder = 0;
        std::vector<uint32_t> new_blocks;

        // Divide by 10, collect remainder
        for (int i = temp.blocks.size() - 1; i >= 0; --i) {
            uint64_t current = (remainder << 32) + temp.blocks[i];
            uint32_t digit = static_cast<uint32_t>(current / 10);
            remainder = current % 10;
            if (digit != 0 || !new_blocks.empty()) {
                new_blocks.push_back(digit);
            }
        }

        // Reverse to maintain little-endian order
        std::reverse(new_blocks.begin(), new_blocks.end());
        temp.blocks = new_blocks;
        result += static_cast<char>('0' + remainder);
    }

    // Reverse to get correct decimal order
    std::reverse(result.begin(), result.end());
    if (is_negative) {
        result.insert(result.begin(), '-');
    }
    return result;
}

Quick Example Usage #

int main() {
    BigNumber num1("123456789012345678901234567890");
    BigNumber num2("987654321098765432109876543210");

    std::cout << "Addition: " << (num1 + num2).to_string() << std::endl;
    std::cout << "Subtraction: " << (num2 - num1).to_string() << std::endl;
    std::cout << "Multiplication: " << (num1 * num2).to_string() << std::endl;
    std::cout << "Division: " << (num2 / num1).to_string() << std::endl;

    return 0;
}

内容的提问来源于stack exchange，提问作者Victor Kataev