Entero grande en C++
En este tutorial, discutiremos el manejo de números enteros grandes en C++. Primero, discutiremos los tipos de enteros primitivos y su rango en C++, luego discutiremos cómo manejar enteros más grandes que los límites de los tipos de enteros primitivos.
Tipos de datos enteros en C++
La siguiente tabla tiene la lista de tipos de datos primitivos en C++. La primera columna tiene tipos de datos, la segunda columna tiene su tamaño en bytes y la última columna tiene el rango máximo de enteros posibles para almacenar en cada tipo de datos.
| Tipo de datos | Tamaño en bytes | Rango |
|---|---|---|
int corto |
2 | -32.768 a +32.767 |
int corto sin firmar |
2 | 0 a +65,535 |
int |
4 | -2.147.483.648 a +2.147.483.647 |
int sin firmar |
4 | 0 a 4,294,967,295 |
int largo |
4 | -2.147.483.648 a +2.147.483.647 |
int largo sin firmar |
4 | 0 a 4,294,967,295 |
largo largo int |
8 | -9.223.372.036.854.775.808 a 9.223.372.036.854.775.807 |
sin firmar largo largo int |
8 | 0 a 18.446.744.073.709.551.615 |
Si tiene alguna confusión sobre el rango, puede verificar, almacenar más grande que el rango en un tipo específico y ver el resultado imprimiendo la misma variable; aquí, estamos dando sólo un ejemplo.
#include <iostream>
using namespace std;
int main() {
short int x = 35000;
cout << x << '\n';
return 0;
}
Producción :
-30536
Puede que se sorprenda al ver los resultados; sin embargo, puede rastrear fácilmente el valor 35000 hasta -30536, utilizando el concepto de almacenamiento de complemento a dos.
De todos modos, saltando al último tipo de datos, unsigned long long int de tamaño 8 bytes.
El número máximo que podemos almacenar en unsigned long long int es 18,446,744,073,709,551,615. El número de dígitos en este número es 20.
Por lo tanto, no podemos almacenar un número que tenga más de 20 dígitos en un tipo de datos primitivo, mientras que es posible que tengamos que manejar números enteros más grandes que los denominados números enteros grandes.
Entero grande en C++
En C++, podemos almacenar Big Integer de gran tamaño. Por ejemplo, podemos manejar un número entero muy grande de 500 dígitos o incluso más en una matriz char, donde cada dígito se almacena como un elemento de carácter.
Antes de la implementación completa de la clase BigInteger, analicemos los componentes más pequeños para una mejor comprensión, comenzando con los miembros de datos de la clase.
char *digit;
int length;
Miembro de datos longitud para almacenar el número de dígitos en Big Integer. La matriz de caracteres dígito es para almacenar dígitos de Big Integer.
A continuación, vea el 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];
}
Este constructor recibe un Big Integer en la matriz char (entrada del usuario o archivo). La función findLength calcula el número de dígitos en Big Integer.
Según la longitud, se declara una matriz dinámica para almacenar dígitos.
Por último, almacenamos los dígitos en orden inverso, por lo que los dígitos de menor orden deben tener un índice más bajo. Este patrón de almacenamiento está diseñado a propósito para hacer que las operaciones aritméticas sean más prácticas.
A continuación, vea el operador de inserción de flujo.
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;
}
Para imprimir números enteros, imprimimos dígitos de mayor a menor orden de izquierda a derecha, ya que normalmente representamos números de izquierda a derecha. Finalmente, vea la implementación completa de la clase BigInteger con el operador sobrecargado más +.
#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;
}
Analicemos rápidamente el operador más. Tenemos dos posibilidades para dos operandos de un entero grande.
Ambos operandos pueden ser del mismo tamaño o de diferentes tamaños.
Los estamos cubriendo a ambos, asumiendo la posibilidad de diferentes tamaños. Por lo tanto, hemos tomado el entero grande resultante de longitud mayor que el tamaño del operando más grande para almacenar carry (puede o no ser necesario).
Estamos ejecutando un ciclo para enteros de menor tamaño. Después de eso, extraemos caracteres de ambos operandos restando el carácter '0' de cada elemento porque el código ASCII del dígito 3 es 51 y el código ASCII del dígito 0 es 48.
Por lo tanto, si restamos 48 de 51, obtendremos 3, que es necesario para la operación de suma.
A continuación, tenga en cuenta que la variable carry se utiliza además de la expresión. Al inicio, el valor contable es 0; sin embargo, al sumar dos dígitos, el resultado puede exceder 9, lo que resulta en un acarreo.
En el primer bucle, estamos manejando dígitos de ambos operandos y almacenando el acarreo en una variable carry utilizada en la siguiente operación de suma.
Después del primer ciclo, debemos decidir cuál de los dos operandos es el más grande. Después de esta selección, almacenamos los dígitos del entero más grande restante en el resultado.
Sin embargo, estamos tomando llevar a lo largo de la expresión.
La razón es que si tenemos 9999...9 en los dígitos restantes y tenemos 1 acarreo de la operación anterior, hará que todos los dígitos del resultado sean 0, y al final, tener una adición de 1 en la respuesta.
Por último, la función principal muestra un ejemplo de dos números enteros grandes que tienen más de cuarenta dígitos. Estamos imprimiendo ambos enteros grandes, y luego los estamos sumando e imprimiendo el resultado.
Producción :
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
71555555555555555555555555555555555555555555555
En la salida, hemos impreso con éxito ambos números enteros grandes. Además, hemos realizado la suma con éxito.
Hemos tomado dos enteros tales que el resultado se verificará fácilmente. Por último, también hemos dado un operador de resta.
// 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;
}
No vamos a entrar en la discusión del operador de resta; sin embargo, una suposición central es que el segundo operando siempre será mayor o igual que el primer operando.
Una última cuestión es la complejidad del espacio. Actualmente, nuestra implementación necesita N bytes para almacenar varios dígitos N (ya que requiere un espacio de caracteres para cada dígito).
Sin embargo, podemos reducir este espacio almacenando dos dígitos en un carácter en lugar de almacenar un dígito en un carácter. Esto puede ahorrar casi la mitad del espacio.
Veamos la implementación de esta 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;
}
Producción :
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
Espero que tenga la idea de manejar Big Integer en C++, y ahora puede implementar el operador más en esta implementación.