Addition of large numbers (C language)

【 introduce 】

In reality , When adding two super large integers , These two super large numbers and their results cannot be stored in variables . But we can use arrays or strings to store , And then, on this basis, we do some operations .

Array + Integers

【 Title Description 】

For non negative integers X for ,X The array form of is an array of each number from left to right . for example , If X = 1231, So its array form is [1,2,3,1].
Given a nonnegative integer X The array form of A, Return integer X+K The array form of .

Title source （ Power button ）： The addition of integers in the form of arrays

Solution 1

The basic idea ： Is the vertical calculation of addition , Add bit by bit , Full decimal one . This solution stores the carry as a variable alone .
notes ：a + b = c（ hypothesis a yes M digit ,b yes N digit , And M > N）,c yes M Number of digits or M + 1 digit , in other words c At most M + 1 digit .
such as 999 + 999 = 1998 , 1998 It's four digits .

void reverseArray(int* num, int numSize)
{
    
    int left = 0, right = numSize - 1;
	while (left < right)
	{
    
		int tmp = num[left];
		num[left] = num[right];
		num[right] = tmp;
		left++;
		right--;
	}
}

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
    
	int kSize = 0;
	int kNum = k;
	while (kNum)    
	{
    
		kSize++;
		kNum /= 10;
	}                 // The above code is to calculate  k  How many digits is it 

	int maxlen = numSize > kSize ? numSize : kSize;
	int* retArr = (int*)malloc(sizeof(int)*(maxlen + 1)); 
	int reti = 0;

	int numi = numSize - 1;
	int nextNum = 0; // carry 
	while (maxlen--)
	{
    
		/*int sum = (num[numi] + k % 10 + nextNum) % 10; nextNum = (num[numi] + k % 10 + nextNum) / 10; numi--;*/
		
		**********************
		int a = 0;
		if (numi >= 0)
		{
    
			a = num[numi];   // Here's a description 
			numi--;
		}
		
		int sum = (a + k % 10 + nextNum) % 10;
		nextNum = (a + k % 10 + nextNum) / 10;
		**********************
		k /= 10;
		
		retArr[reti++] = sum;
	}

	if (nextNum == 1)  // The above cycle is over , There is also carry . such as ：99 + 62 = 161
	{
    
		retArr[reti++] = 1;
	}

	reverseArray(retArr, reti);
	*returnSize = reti;
	return retArr;
}

explain ：while (k–) It's a cycle k Time .
and while (–k) It's a cycle k - 1 Time .
Here we want it to cycle k Time , Thus using while (k–) To control .

explain ： Can not write /**/ Between , To write “ ******* ” Between . reason ： When k The digit ratio of num[] When the number of digits is larger , An array cross-border access will occur .
Because we put the result of each addition upside down into the array , So we need to reverse the array .
We can't just stare at the examples given when we brush the questions , The examples it gives are generally more conventional , More often, we have to consider less conventional situations .

notes ： ad locum , Some of us may not understand why we should give parameters int* returnSize, I don't know what it's for .
Actually , When the function returns a int* When the pointer , If it represents an array , Functions usually have parameters int* returnSize.
When this function is called , Will give variables （ Here I assume that the variable name is size ） The address of is passed in as a parameter , After function execution ,size The value of should be the size of the array returned by the function .
Do you think so? , without int* returnSize This parameter , Then you don't know the size of the array returned by the function , Therefore, it is possible to cross the bounds when accessing the elements of this array .（ To be exact , I don't even know where the bounds of the array are ）

Solution 2

This solution adds a carry to an integer k On .

int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
    
	int kSize = 0;
	int kNum = k;
	while (kNum)    // Calculation k How many digits is it 
	{
    
		kSize++;
		kNum /= 10;
	}

	int maxlen = numSize > kSize ? numSize : kSize;
	int* retArr = (int*)malloc(sizeof(int)*(maxlen + 1));
	int reti = 0;

	for(int i = numSize - 1; i >=0; i--)
	{
    
		int sum = num[i] + k % 10;
		k /= 10;
		if(sum > 9)
		{
    
			k++;
			sum -= 10;
		}
		
		retArr[reti++] = sum;
	}
	
	while(k) // Here's a description 
	{
    
		retArr[reti++] = k % 10;
		k /= 10;
	}
	
	reverseArray(retArr, reti);
	*returnSize = reti;
	return retArr;
}

explain ： In response k The digit ratio of num[] When the number of digits is large , Wrote the last while loop . Put the extra k The first few digits of are directly copied to the array .

Array + Array

The overall idea is the same as the above Solution 1 It's the same , Just add them in the form of an array .

void reverseArray(int* num, int numSize)
{
    
    int left = 0, right = numSize - 1;
	while (left < right)
	{
    
		int tmp = num[left];
		num[left] = num[right];
		num[right] = tmp;
		left++;
		right--;
	}
}

int* addArrays(int* num1, int num1Size, int* num2, int num2Size, int* returnSize)
{
    
	int maxlen = num1Size > num2Size ? num1Size : num2Size;
	int* retArr = (int*)malloc(sizeof(int)*(maxlen + 1));
	int reti = 0;

	int num1i = num1Size - 1, num2i = num2Size - 1;
	int nextNum = 0; // carry 
	while (maxlen--)
	{
    
		int a = 0;
		if (num1i >= 0)
		{
    
			a = num1[num1i];
			num1i--;
		}

		int b = 0;
		if (num2i >= 0)
		{
    
			b = num2[num2i];
			num2i--;
		}
		
		int sum = (a + b + nextNum) % 10;
		nextNum = (a + b + nextNum) / 10;
		
		retArr[reti++] = sum;
	}

	if (nextNum == 1)
	{
    
		retArr[reti++] = 1;
	}

	reverseArray(retArr, reti);
	*returnSize = reti;
	return retArr;
}

character string + character string

Here we need to know such a point first , Namely How to convert a character number to an integer number .
‘9’ - ‘0’ == 9
Just subtract the characters from the character numbers 0 that will do , Their ASCII The difference of the code is the result we want .

【 Title Description 】

Given two non negative integers in string form num1 and num2 , Calculate their sum and return as a string .

You can't use any built-in library for handling large integers （ such as BigInteger）, You can't directly convert the input string to integer form .

Title source （ Power button ）： String addition

void reverseString(char* str, int len)
{
    
	int left = 0, right = len - 1;
	while (left < right)
	{
    
		char tmp = str[left];
		str[left] = str[right];
		str[right] = tmp;
		left++;
		right--;
	}
}

char * addStrings(char * num1, char * num2) {
    
	int maxlen = strlen(num1) > strlen(num2) ? strlen(num1) : strlen(num2);
	char* retStr = (char*)malloc(sizeof(char)*(maxlen + 2)); 
	// Because this is a string , There's still something to put in the back '\0', So it's not  maxlen + 1, It is  maxlen + 2
	int reti = 0;

	int num1i = strlen(num1) - 1;
	int num2i = strlen(num2) - 1;
	int nextNum = 0;
	while (maxlen--)
	{
    
		char m = '0';
		if (num1i >= 0)
		{
    
			m = num1[num1i];
			num1i--;
		}

		char n = '0';
		if (num2i >= 0)
		{
    
			n = num2[num2i];
			num2i--;
		}

		int sum = ((m - '0') + (n - '0') + nextNum) % 10;
		nextNum = ((m - '0') + (n - '0') + nextNum) / 10;

		retStr[reti++] = '0' + sum;

	}

	if (nextNum == 1)
	{
    
		retStr[reti++] = '1';
	}

	retStr[reti] = '\0';

	reverseString(retStr, strlen(retStr));
	return retStr;
}

Because we're going to % and / Arithmetic , It is not possible to use character numbers , Because the operation of character numbers is essentially ASCII The operation of codes , And the character type number ASCII Codes and character numbers do not absolutely correspond to each other （ such as ‘0’ Of ASCII Code is 48 , instead of 0 ）.

More articles
Merge two ordered arrays （C Language ）
Zero after factorial （C Language ）
Adjust the array order so that the odd Numbers precede the even Numbers （C Language ）