C++의 큰 정수
이 자습서에서는 C++에서 큰 정수를 처리하는 방법에 대해 설명합니다. 먼저 기본 정수 유형과 C++의 범위에 대해 논의한 다음 기본 정수 유형의 한계보다 큰 정수를 처리하는 방법에 대해 논의합니다.
C++의 정수 데이터 유형
다음 표에는 C++의 기본 데이터 유형 목록이 있습니다. 첫 번째 열에는 데이터 유형이 있고 두 번째 열에는 바이트 단위의 크기가 있으며 마지막 열에는 각 데이터 유형에 저장할 수 있는 정수의 최대 범위가 있습니다.
| 데이터 형식 | 크기(바이트) | 범위 |
|---|---|---|
짧은 정수 |
2 | -32,768 ~ +32,767 |
부호 없는 짧은 int |
2 | 0 ~ +65,535 |
int |
4 | -2,147,483,648 ~ +2,147,483,647 |
부호 없는 정수 |
4 | 0 ~ 4,294,967,295 |
긴 정수 |
4 | -2,147,483,648 ~ +2,147,483,647 |
부호 없는 긴 정수 |
4 | 0 ~ 4,294,967,295 |
긴 긴 정수 |
8 | -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 |
unsigned long long int |
8 | 0 ~ 18,446,744,073,709,551,615 |
범위에 대해 약간의 혼란이 있는 경우 특정 유형의 범위보다 큰 범위를 확인하고 저장하고 동일한 변수를 인쇄하여 결과를 볼 수 있습니다. 여기서는 한 가지 예만 제공합니다.
#include <iostream>
using namespace std;
int main() {
short int x = 35000;
cout << x << '\n';
return 0;
}
출력:
-30536
결과를 보고 놀랄 수도 있습니다. 그러나 2의 보수 저장 개념을 사용하여 값 35000에서 -30536까지 쉽게 추적할 수 있습니다.
어쨌든 마지막 데이터 유형인 8바이트 크기의 unsigned long long int로 이동합니다.
unsigned long long int에 저장할 수 있는 최대 수는 18,446,744,073,709,551,615입니다. 이 숫자의 자릿수는 20입니다.
따라서 20자리가 넘는 숫자는 원시 데이터 형식으로 저장할 수 없지만, 큰 정수라고 하는 것보다 큰 정수를 처리해야 할 수도 있습니다.
C++의 큰 정수
C++에서는 거대한 크기의 Big Integer를 저장할 수 있습니다. 예를 들어, 각 숫자가 하나의 문자 요소로 저장되는 char 배열에서 500자리 이상의 매우 큰 정수를 처리할 수 있습니다.
BigInteger 클래스를 완전히 구현하기 전에 더 나은 이해를 위해 클래스의 데이터 멤버부터 시작하여 더 작은 구성 요소에 대해 논의해 봅시다.
char *digit;
int length;
Big Integer에 자릿수를 저장하는 데이터 멤버 length. 문자 배열 숫자는 Big Integer의 숫자를 저장하는 것입니다.
다음으로 생성자를 참조하십시오.
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];
}
이 생성자는 char 배열(사용자 또는 파일의 입력)에서 Big Integer를 받습니다. findLength 함수는 Big Integer의 자릿수를 계산합니다.
길이에 따라 숫자를 저장하기 위해 동적 배열이 선언됩니다.
마지막으로 숫자를 역순으로 저장하므로 하위 숫자는 하위 색인에 와야 합니다. 이 저장 패턴은 산술 연산을 보다 쉽게 수행할 수 있도록 의도적으로 설계되었습니다.
다음으로 스트림 삽입 연산자를 참조하십시오.
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;
}
정수를 인쇄하려면 일반적으로 왼쪽에서 오른쪽으로 숫자를 나타내므로 높은 순서에서 낮은 순서로 왼쪽에서 오른쪽으로 숫자를 인쇄합니다. 마지막으로 오버로드된 더하기 + 연산자가 있는 BigInteger 클래스의 전체 구현을 확인하십시오.
#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;
}
더하기 연산자에 대해 빠르게 살펴보겠습니다. 큰 정수의 두 피연산자에 대해 두 가지 가능성이 있습니다.
두 피연산자의 크기는 같거나 다를 수 있습니다.
서로 다른 크기의 가능성을 가정하여 두 가지를 모두 다루고 있습니다. 따라서 carry를 저장하기 위해 더 큰 피연산자의 크기보다 더 큰 길이의 결과적인 큰 정수를 취했습니다(필요할 수도 있고 필요하지 않을 수도 있음).
더 작은 크기의 정수에 대한 루프를 실행하고 있습니다. 그런 다음 숫자 3의 ASCII 코드가 51이고 숫자 0의 ASCII 코드가 48이므로 각 요소에서 '0' 문자를 빼서 두 피연산자에서 문자를 추출합니다.
따라서 51에서 48을 빼면 더하기 연산에 필요한 3이 됩니다.
다음으로 변수 carry를 가산식에 사용합니다. 처음에는 장부가가 0입니다. 그러나 두 자릿수를 더하면 결과가 9를 초과하여 캐리가 될 수 있습니다.
첫 번째 루프에서 두 피연산자의 숫자를 처리하고 다음 추가 연산에 사용되는 carry 변수에 캐리를 저장합니다.
첫 번째 루프 후에 두 피연산자 중 어느 것이 큰 피연산자인지 결정해야 합니다. 이 선택 후에 나머지 더 큰 정수의 숫자를 결과에 저장합니다.
그러나 우리는 표현 전체에서 carry를 취하고 있습니다.
그 이유는 나머지 숫자에 9999...9가 있고 이전 작업에서 1이 있으면 결과의 모든 숫자가 0이 되고 마지막에 우리는 대답에 1을 추가하십시오.
마지막으로, main 함수는 40개 이상의 자릿수를 갖는 두 개의 큰 정수의 예를 보여줍니다. 우리는 두 개의 큰 정수를 인쇄하고 나중에 더하고 결과를 인쇄합니다.
출력:
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
71555555555555555555555555555555555555555555555
출력에서 두 개의 큰 정수를 모두 성공적으로 인쇄했습니다. 또한 추가를 성공적으로 수행했습니다.
결과를 쉽게 확인할 수 있도록 두 개의 정수를 취했습니다. 마지막으로 빼기 연산자도 제공했습니다.
// 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;
}
우리는 빼기 연산자에 대해 논의하지 않을 것입니다. 그러나 한 가지 중요한 가정은 두 번째 피연산자가 항상 첫 번째 피연산자보다 크거나 같다는 것입니다.
마지막 문제는 공간 복잡성입니다. 현재 우리의 구현에는 여러 개의 N 숫자를 저장하기 위해 N 바이트가 필요합니다(각 숫자에 대한 문자 공간이 필요하기 때문).
그러나 하나의 문자에 하나의 숫자를 저장하는 대신 하나의 문자에 두 개의 숫자를 저장하여 이 공간을 줄일 수 있습니다. 이것은 거의 절반의 공간을 절약할 수 있습니다.
이 아이디어의 구현을 살펴보겠습니다.
#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;
}
출력:
67234321234321234321234321234321234321234321234
4321234321234321234321234321234321234321234321
C++에서 Big Integer를 처리하는 아이디어를 얻었기를 바라며 이제 이 구현에서 더하기 연산자를 구현할 수 있습니다.