Big Integer in C++
In this tutorial, we will discuss handling big integers in C++. First, we will discuss primitive integer types and their range in C++ then we will discuss how to handle integers larger than the limits of primitive integer types.
Integer Data Types in C++
The following table has the list of primitive data types in C++. The first column has data types, the second column has their size in bytes, and the last column has the maximum range of integers possible to store in each data type.
| Data Type | Size in Bytes | Range |
|---|---|---|
short int |
2 | -32,768 to +32,767 |
unsigned short int |
2 | 0 to +65,535 |
int |
4 | -2,147,483,648 to +2,147,483,647 |
unsigned int |
4 | 0 to 4,294,967,295 |
long int |
4 | -2,147,483,648 to +2,147,483,647 |
unsigned long int |
4 | 0 to 4,294,967,295 |
long long int |
8 | -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 |
unsigned long long int |
8 | 0 to 18,446,744,073,709,551,615 |
If you have some confusion about the range, you may check, store larger than the range in a specific type and see the result by printing the same variable; here, we are giving only one example.
#include <iostream>
using namespace std;
int main() {
short int x = 35000;
cout << x << '\n';
return 0;
}
Output:
-30536
You might be amazed to see the results; however, you can easily trace the value 35000 to -30536, using two’s complement storage concept.
Anyhow, jumping to the last data type, unsigned long long int of size 8 bytes.
The maximum number, we can store in unsigned long long int is 18,446,744,073,709,551,615. The number of digits in this number is 20.
Therefore, we can’t store a number having more than 20 digits in primitive data type, whereas we may have to handle integers larger than that referred to as big integers.
Big Integer in C++
In C++, we can store Big Integer of huge size. For example, we can handle a very large integer of 500 digits or even more in a char array, where each digit is stored as one character element.
Before the complete implementation of the BigInteger class, let’s discuss smaller constituents for a better understanding, starting with data members of the class.
char *digit;
int length;
Data member length to store the number of digits in Big Integer. Character array digit is to store digits of Big Integer.
Next, see the constructor.
BigInteger(const char integer[]) {
length = findLength(integer);
digit = new char[length];
for (int i = length - 1, j = 0; i >= 0; i--) digit[j++] = integer[i];
}
This constructor receives a Big Integer in the char array (input from the user or file). The findLength function calculates the number of digits in Big Integer.
According to length, a dynamic array is declared to store digits.
Lastly, we store digits in reverse order, so lower-order digits should come at a lower index. This storage pattern is purposefully designed to make arithmetic operations handier.
Next, see the stream insertion operator.
friend ostream &operator<<(ostream &out, const BigInteger &integer) {
for (int i = integer.length - 1; i >= 0; i--) out << integer.digit[i];
out << '\n';
return out;
}
To print integers, we print digits from higher order to lower order from left to right, as we normally represent numbers from left to right. Finally, see the complete implementation of the BigInteger class with the overloaded plus + operator.
#include <iostream>
using namespace std;
class BigInteger {
char *digit;
int length;
int findLength(const char integer[]) {
int length = 0;
for (; integer[length] != 0; length++)
;
return length;
}
public:
BigInteger(const int SIZE) {
// This constructor is used to store results, and the length will be
// determined later
length = 0;
digit = new char[SIZE];
}
BigInteger(const char integer[]) {
length = findLength(integer);
digit = new char[length];
// store digits left to right, store higher order digits on higher index
for (int i = length - 1, j = 0; i >= 0; i--) digit[j++] = integer[i];
}
BigInteger operator+(const BigInteger &secondInteger) {
// Take i,j for loop, take the carry to store carry of the addition
// operation At the start, set carry to 0; in the process of addition, we
// will get carry
int i, j, result, carry = 0; // result to store sum of addition of digits
// Find the length of a longer integer
int length = this->length;
if (length < secondInteger.length) length = secondInteger.length;
// Take variable answer, set its length greater than the length of longer
// integer The result may have carry, which makes size greater than existing
// integers
BigInteger answer(length + 1);
for (i = 0; i < this->length && i < secondInteger.length; i++) {
result = this->digit[i] + secondInteger.digit[i] + carry - '0' - '0';
carry = result / 10;
answer.digit[i] = result % 10 + '0';
}
// Take a pointer and point it to a long integer
const BigInteger *currentInteger = this;
if (currentInteger->length < secondInteger.length)
currentInteger = &secondInteger;
// Add remaining digits to answer
for (; i < currentInteger->length; i++) {
result = currentInteger->digit[i] + carry - '0';
carry = result / 10;
answer.digit[i] = result % 10 + '0';
}
// set the length of an answer now
answer.length = length + 1;
// Check if there is carry or not
if (carry == 0)
length--; // reduce length because there is no carry
else
answer.digit[i] = carry + '0';
return answer;
}
friend ostream &operator<<(ostream &out, const BigInteger &integer) {
for (int i = integer.length - 1; i >= 0; i--) out << integer.digit[i];
out << '\n';
return out;
}
};
int main() {
BigInteger integer1("67234321234321234321234321234321234321234321234");
BigInteger integer2("4321234321234321234321234321234321234321234321");
cout << integer1 << integer2;
cout << integer1 + integer2;
return 0;
}
Let’s quickly discuss the plus operator. We have two possibilities for two operands of a big integer.
Both operands can be of the same size or different sizes.
We are covering both of them, assuming the possibility of different sizes. Therefore, we have taken the resultant big integer of length greater than the size of the larger operand to store carry (may or may not be required).
We are running a loop for smaller-sized integers. After that, we extract characters from both operands by subtracting the '0' character from each element because the ASCII code of digit 3 is 51 and the ASCII code of digit 0 is 48.
Therefore, if we subtract 48 from 51, we will get 3, which is required for the addition operation.
Next, note variable carry is used in addition expression. At the start, the carrying value is 0; however, by adding two digits, the result may exceed 9, resulting in a carry.
In the first loop, we are handling digits of both operands and storing carry in a variable carry used in the next addition operation.
After the first loop, we must decide which of the two operands is the large one. After this selection, we store digits of the remaining larger integer in the result.
However, we are taking carry throughout the expression.
The reason is that if we have 9999...9 in the remaining digits and we have 1 carry from the previous operation, it will make all the digits of the result 0, and at the end, we will have an addition of 1 in the answer.
Lastly, the main function shows an example of two big integers having forty-plus digits. We are printing both big integers, and later we are adding them and printing the result.
Output:
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
71555555555555555555555555555555555555555555555
In the output, we have successfully printed both big integers. Also, we have performed addition successfully.
We have taken two integers such that the result will be easily verified. Lastly, we have given a subtraction operator as well.
// Here, we are assuming that we are handling positive integers only
// Therefore, the first integer should be larger or equal to the second integer
BigInteger operator-(const BigInteger &secondInteger) {
// First store result in a temporary array and later create answer object
// accordingly
int operand1, operand2;
int i, j, result, carry = 0; // result to store sum of addition of digits
// length of the first object will always be greater than equal to second
char *diff = new char[this->length];
// Copy elements of the first operand into a temporary array
for (i = 0; i < this->length; i++) diff[i] = this->digit[i];
// Now take a difference of diff array with the second integer
for (i = 0; i < secondInteger.length; i++) {
operand1 = diff[i] - '0';
operand2 = secondInteger.digit[i] - '0';
if (operand1 < operand2) {
operand1 += 10; // In subtraction carry is always 10
for (j = i + 1; diff[j] == 0; j++)
;
// at left larger than 0 digits always exist
diff[j]--; // Take 1 carry from left non-zero digit
for (j--; j > i; j--) // shift carry to right
diff[j] = 9;
operand1 += 10; // Add 10 to current digit to create effect of carry
}
result = operand1 - operand2;
diff[i] = result + '0';
}
// Find the length of array difference by finding the leading zero digits on
// the left side
int length = this->length;
for (; length >= 0 && diff[length] != 0; length--)
;
BigInteger answer(&diff[length]);
return answer;
}
We are not going into the discussion of the subtraction operator; however, one central assumption is that the second operand will always be greater than or equal to the first operand.
One final issue is space complexity. Currently, our implementation needs N bytes to store several N digits (as it requires a character space for each digit).
However, we may reduce this space by storing two digits in one character instead of storing one digit in one character. This can save almost half of the space.
Let’s look at the implementation of this idea.
#include <iostream>
using namespace std;
class BigInteger {
char* digit;
int digitsCount, bytesCount;
int findLength(const char integer[]) {
int length = 0;
for (; integer[length] != 0; length++)
;
return length;
}
public:
BigInteger(const char integer[]) {
digitsCount = findLength(integer);
if (digitsCount % 2 == 0)
bytesCount = digitsCount / 2;
else
bytesCount = digitsCount / 2 + 1;
digit = new char[bytesCount];
int i = digitsCount - 1, j = 0;
// Handle n - 1 digit in a loop
for (; i > 0; i -= 2) {
// After subtracting 48 or ASCII of 0, the result will be in the right 4
// bits only
digit[j] = (integer[i] - '0'); // In first 4 bits store even integer
digit[j++] +=
((integer[i - 1] - '0') << 4); // In last 4 bits store odd integer
}
// Handle the last digit separately in case of an odd number of digits only
if (digitsCount % 2 == 1) digit[j] = (integer[i] - '0');
}
friend ostream& operator<<(ostream& out, const BigInteger& integer) {
int i = integer.bytesCount - 1;
if (integer.digitsCount % 2 == 1) {
out << (int)integer.digit[i];
i--;
}
for (; i >= 0; i--)
out << ((integer.digit[i] & 0xF0) >> 4) << (integer.digit[i] & 0x0F);
out << '\n';
return out;
}
};
int main() {
BigInteger integer1("67234321234321234321234321234321234321234321234");
BigInteger integer2("4321234321234321234321234321234321234321234321");
cout << integer1 << integer2;
return 0;
}
Output:
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
Hope you have got the idea of handling Big Integer in C++, and now you can implement the plus operator in this implementation.