如何为基于数组实现的C++ bigint类重载+运算符？

Hey there! Let's walk through exactly how to implement the addition operator for your bigint class—since you're storing digits from least significant to most (e.g., 201 becomes [1, 0, 2]), we can model this just like how we do manual addition: start at the lowest digit, sum, and carry over as needed.

First, Let's Outline the BigInt Class Structure #

First, let's define a simplified version of your class to ground our example. We'll focus on the core components needed for addition:

#include <algorithm> // for std::max
#include <iostream>

class bigint {
private:
    int* digits;    // Stores digits, least significant first
    int size;       // Number of valid digits in the array
    int capacity;   // Total allocated capacity of the array

public:
    // Basic constructor (initializing with a small int)
    bigint(long long num = 0) {
        capacity = 10; // Start with a small default capacity
        digits = new int[capacity](); // Initialize all elements to 0
        size = 0;
        
        if (num == 0) {
            digits[size++] = 0;
            return;
        }
        
        while (num > 0) {
            digits[size++] = num % 10;
            num /= 10;
        }
    }

    // Destructor to clean up memory
    ~bigint() {
        delete[] digits;
    }

    // Copy constructor (avoids shallow copy issues)
    bigint(const bigint& other) {
        capacity = other.capacity;
        size = other.size;
        digits = new int[capacity]();
        for (int i = 0; i < size; ++i) {
            digits[i] = other.digits[i];
        }
    }

    // Assignment operator
    bigint& operator=(const bigint& other) {
        if (this == &other) return *this;
        
        delete[] digits;
        capacity = other.capacity;
        size = other.size;
        digits = new int[capacity]();
        for (int i = 0; i < size; ++i) {
            digits[i] = other.digits[i];
        }
        return *this;
    }

    // Helper to get a digit (returns 0 if index is out of bounds)
    int get_digit(int index) const {
        return (index < size) ? digits[index] : 0;
    }

    // Print function to verify results (outputs most significant first)
    void print() const {
        for (int i = size - 1; i >= 0; --i) {
            std::cout << digits[i];
        }
        std::cout << std::endl;
    }

    // The + operator overload we care about!
    bigint operator+(const bigint& other) const;
};

Implementing the + Operator #

Now let's write the actual addition logic. The key steps are:

1. Calculate the maximum possible size of the result (larger of the two input sizes + 1 for potential final carry)
2. Iterate over each digit position, sum the digits from both numbers plus any carry
3. Store the least significant digit of the sum in the result
4. Update the carry for the next position
5. Handle any remaining carry after processing all digits

Here's the code:

bigint bigint::operator+(const bigint& other) const {
    bigint result;
    int max_input_size = std::max(size, other.size);
    
    // Ensure result has enough capacity for max size + 1 (for carry)
    if (result.capacity < max_input_size + 1) {
        delete[] result.digits;
        result.capacity = max_input_size + 1;
        result.digits = new int[result.capacity]();
    }
    
    int carry = 0;
    result.size = 0;

    // Loop until we've processed all digits AND there's no carry left
    for (int i = 0; i < max_input_size || carry != 0; ++i) {
        int total = get_digit(i) + other.get_digit(i) + carry;
        result.digits[result.size++] = total % 10; // Store the current digit
        carry = total / 10; // Calculate new carry for next iteration
    }

    return result;
}

Testing the Implementation #

Let's test this with your example and a common edge case:

int main() {
    bigint a(201); // Stored as [1, 0, 2]
    bigint b(199); // Stored as [9, 9, 1]
    
    bigint sum = a + b; // Should be 400, stored as [0, 0, 4]
    std::cout << "201 + 199 = ";
    sum.print(); // Outputs: 400

    // Test edge case: 999 + 1 = 1000
    bigint c(999);
    bigint d(1);
    bigint sum2 = c + d;
    std::cout << "999 + 1 = ";
    sum2.print(); // Outputs: 1000

    return 0;
}

Key Notes to Remember #

• Memory Management: Since we're using raw arrays, always implement the rule of three (copy constructor, assignment operator, destructor) to avoid memory leaks and shallow copy bugs.
• Capacity Handling: In the example above, we adjust the result's capacity as needed. For a more robust implementation, you could add a helper function to resize the array dynamically when it's full.
• Negative Numbers: If you plan to support negative integers later, you'll need to add a sign flag and adjust the addition logic to handle subtraction when signs differ.

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