Detailed explanation of the code of C++ implementing large number multiplication problem based on strings

1. Problem description

In actual programming, we often encounter situations where we need to deal with large integers. Due to built-in integer types in programming languages ​​(such asint、longetc.) has its limitations on representing the range. When the integers that need to be processed exceed these ranges, it cannot be directly calculated using built-in types.
The general solution is to use two non-negative integers expressed in string form.num1andnum2multiplication and return the result as a string.

Input Limits

• 1 <= , <= 200
• num1andnum2It can only be composed of numbers.
• num1andnum2Not including any leading zeros except numbers0Original.

2. Problem-solving ideas

To solve this problem, we can simulate the process of manual multiplication. In manual multiplication, we multiply each bit of one number with each bit of another number, then add the results and process the carry. The specific steps are as follows:

1. Special circumstances handling:ifnum1ornum2for"0", then return directly"0"。
2. Invert string: In order to facilitate calculations from low to high, we willnum1andnum2Reversal.
3. Initialize the result array: Create a length of() + ()Array ofret, used to store intermediate results. Because the result number of digits multiplied by two numbers will not exceed the sum of the digits of these two numbers.
4. Multiply by bit: Use two-layer loops tonum1Every one of them andnum2Multiply each bit of   and accumulate the result toretThe corresponding position of the array.
5. Handle carry:TravelretArray, add the carry of each bit to the next.
6. Remove leading zeros: Since the result array may have leading zeros, we need to remove them.
7. Convert to string: Convert the processed result array into a string.

3. Code implementation

#include <string>
#include <algorithm>

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        // First determine whether there is one that is 0        if(num1 == "0" || num2 == "0")
            return "0";

        // Invert two strings to facilitate operation        reverse((), ());
        reverse((), ());

        // The number of result digits does not exceed the sum of two strings        int size = () + ();

        // Create an array that stores the results and initialize it to 0        int* ret = new int[size]();
        
        // Multiply strings without taking into account carry        for(int i = 0; i < (); ++i)
        {
            for(int j = 0; j < (); ++j)
            {
                ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        // Handle carry        for(int i = 0; i < size - 1; ++i)
        {
            ret[i + 1] += ret[i] / 10;
            ret[i] = ret[i] % 10;
        }
        
        // Remove leading zeros        int i = size - 1;
        while( (ret[i] == 0) && (size > 1) )
        {
            --size;
            --i;
        }

        // Turn string        string s = "";
        (size);
        for(int i = size - 1; i >= 0; --i)
        {
            s += ('0' + ret[i]);
        }

        // Free dynamically allocated memory        delete[] ret;
        return s;
    }
};

4. Detailed code analysis

1. Special circumstances handling

if(num1 == "0" || num2 == "0")
    return "0";

ifnum1ornum2for"0", then their product must be"0", just return directly.

2. Invert the string

reverse((), ());
reverse((), ());

usestd::reverseThe function willnum1andnum2Invert, so that processing can be started from the low bit (the starting position of the string) in subsequent calculations.

3. Initialize the result array

int size = () + ();
int* ret = new int[size]();

Build a length of() + ()The array of integersret, and use()Processing value initialization, and initializing all array elements to 0.

4. Multiply by bit

for(int i = 0; i < (); ++i)
{
    for(int j = 0; j < (); ++j)
    {
        ret[i + j] += (num1[i] - '0') * (num2[j] - '0');
    }
}

Using a two-layer nested loop, thenum1Every one of them andnum2Multiply each bit of   and accumulate the result toretThe corresponding position of the array.(num1[i] - '0')and(num2[j] - '0')is converting characters into corresponding numbers.

5. Handle carry

for(int i = 0; i < size - 1; ++i)
{
    ret[i + 1] += ret[i] / 10;
    ret[i] = ret[i] % 10;
}

TraversalretArray, carry each bit (ret[i] / 10) Add to the next bit, and at the same time, the current bit is modulo 10 to get the final result of that bit.

6. Remove leading zeros

int i = size - 1;
while( (ret[i] == 0) && (size > 1) )
{
    --size;
    --i;
}

Check starting from the highest bit of the result array. If the bit is 0 and the result length is greater than 1, then the length is reduced by 1 and continue to check the previous bit.

7. Convert to string

string s = "";
(size);
for(int i = size - 1; i >= 0; --i)
{
    s += ('0' + ret[i]);
}

Create an empty strings, and usereserveMethod preallocates enough space. Then start from the highest bit of the result array, convert each bit into a character and add it to the string.smiddle.

8. Free memory

delete[] ret;

becauseretIt is a dynamically allocated array, and it needs to be used after use.delete[]Free up memory to avoid memory leakage.

5. Complexity analysis

• Time complexity:O ( m ∗ n ), where m mm and n nn are respectivelynum1andnum2length. The main time overhead lies in the multiplication of two-layer nested loops bit by bit.
• Space complexity:O ( m + n ), the main spatial overhead lies in the array that stores intermediate results.ret。

Through the above steps, we can implement multiplication of two large integers and return the result as a string. This method simulates the process of manual multiplication, avoiding the use of the built-in large integer library and directly converting the input into integers, and is suitable for handling large integer multiplication problems beyond the range of the built-in integer type representation.

The above is the detailed explanation of the code of C++ implementing the problem of multiplication of large numbers based on strings. For more information about C++ strings implementing the multiplication of large numbers, please pay attention to my other related articles!