C++ BigInteger类字符串大数乘法异常：含数字9时出错

Hey there! Let's figure out why your BigInteger multiplication is failing only when digits include 9—this is a super common pitfall with hand-rolled big number implementations, so let's break it down.

The Likely Culprit: Incorrect Carry Handling #

Looking at your code snippet, I notice you're using a char to store the carry value (char carry = '0';). That's probably where the problem lies.

When multiplying digits that include 9, like 99=81, the carry here is 8—but if you have a scenario where you add a previous carry to that product (e.g., 99 + 9 = 90), the carry becomes 90. A char can only hold a single character, so storing a two-digit carry as a char will corrupt the value (it'll turn into an unprintable ASCII character instead of a numeric value). When you later try to convert that corrupted carry back to a digit, you'll get garbage results—hence why your code works fine until 9 is involved.

Other Possible Issues to Check #

• Index Calculation Mistakes: Big number multiplication requires precise indexing to map digit pairs to the correct position in the result string. If you're shifting the index (d) incorrectly, multiplying 9 (which produces larger intermediate values) could overwrite the wrong positions in your tmp string.
• Unfinished Carry After Loops: If you don't handle leftover carry after your nested loops finish, multiplying large digits like 9 might leave an unprocessed carry that never gets added to the result's highest digits.

Corrected Implementation #

Here's a revised version of the multiplication operator that fixes these issues, using integer storage for digits/carry to avoid character conversion errors:

BigInteger& BigInteger::operator*(const BigInteger& rhs) {
    // Handle edge case: multiply by 0
    if (num == "0" || rhs.num == "0") {
        num = "0";
        return *this;
    }

    int len1 = num.size();
    int len2 = rhs.num.size();
    // Use a vector of integers to store intermediate results (avoids char conversion bugs)
    std::vector<int> result(len1 + len2, 0);

    // Iterate from right to left (least significant to most significant digit)
    for (int i = len1 - 1; i >= 0; --i) {
        int digit1 = num[i] - '0'; // Convert char to integer digit
        for (int j = len2 - 1; j >= 0; --j) {
            int digit2 = rhs.num[j] - '0';
            // Calculate total value for this position: product + existing result + carry
            int total = digit1 * digit2 + result[i + j + 1];
            // Update current position with the remainder (0-9)
            result[i + j + 1] = total % 10;
            // Add the carry to the next higher position
            result[i + j] += total / 10;
        }
    }

    // Convert the integer vector back to a string, skipping leading zeros
    std::string tmp;
    bool leading_zero = true;
    for (int digit : result) {
        if (digit == 0 && leading_zero) {
            continue;
        }
        leading_zero = false;
        tmp += (digit + '0'); // Convert integer back to char
    }

    // Fallback in case all digits were zero (shouldn't happen due to earlier check)
    if (tmp.empty()) {
        tmp = "0";
    }

    num = tmp;
    return *this;
}

Key Fixes Explained #

1. Integer-Based Carry/Storage: Using a vector<int> for intermediate results eliminates the risk of char overflow. Every carry and digit is stored as a numeric value, not a character.
2. Precise Indexing: The position i + j + 1 correctly maps the product of the i-th digit of the first number and j-th digit of the second number to its place in the result.
3. Edge Case Handling: Explicitly checks for multiplication by zero to avoid unnecessary computation and ensure correct results.
4. Leading Zero Removal: Cleans up the final string to avoid results like "000123" and returns "123" instead.

This implementation should work reliably for all digits, including 9.

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