C++에서 정말 큰 숫자를 인쇄하는 방법
https://stackoverflow.com/questions/240876
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이 코드가 있습니다
#include <iostream>
using namespace std;
int main(int argc,char **argv) {
unsigned long long num1 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995LL;
unsigned long long num2 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996LL;
unsigned long long num3 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997LL;
unsigned long long num4 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998LL;
unsigned long long num5 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999LL;
cout << (unsigned long long)(num1 * num2 * num3 * num4 * num5) << endl;
return 0;
}
보시다시피 숫자는 엄청나지만 계산을 하면 다음과 같은 결과를 얻습니다.18446744073709551496
컴파일 타임에 다음과 같은 경고가 표시됩니다.
warning: integer constant is too large for its type|
In function `int main(int, char**)':|
warning: this decimal constant is unsigned only in ISO C90|
...
해결책
당신의 결과는 길고 긴 유형보다 큽니다. Biginteger 또는 임의의 정밀 라이브러리 등 GMP
다른 팁
이러한 숫자는 C ++ 데이터 유형에 맞지 않습니다. 인쇄하려면 숫자를 문자열에 저장하십시오. 수학을 원한다면 임의의 정밀 수학 라이브러리를 찾아 사용하십시오.
코드에서 리터럴을 크게 원한다면 문자 리터럴로 입력하여 어떤 종류의 큰 클래스에로드해야합니다. 소스 코드에서 큰 정수 리터럴을 표현하는 방법은 없습니다 (C ++ 0X는 그 부족을 희망적으로 해결할 것입니다).
사용하는 경우 Biginteger 도서관, stringToBigUnsigned 기능 BigIntegerUtils.hh 문자열에서 큰 정수를 구축합니다.
#include "BigUnsigned.hh"
#include "BigIntegerUtils.hh"
BigUnsigned num1 = stringToBigUnsigned (
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999995"
);
당신이하려는 것이 무엇입니까?이진수와 십진수의 기본을 이해하고 있나요?왜 8비트는 0~255, 12비트는 0~4095 등의 값만 보유합니까?관심 있는 숫자를 유지하려면 몇 비트가 필요합니까?아니면 얼마나 큰 숫자를 만드는 데 관심이 있나요?그리고 숫자를 더 크게 만들기 위해 9를 사용하고 있습니까?16진수 0xF는 어떻습니까?대신에?표준 정수 유형 중 하나 내에서 가장 큰 부호 없는 숫자를 원한다면 다음을 수행하면 됩니다.
부호 없는 긴 긴 a,b;
a = -1;//부호 있는 것과 부호 없는 것을 혼합하는 것이 잘못된 것 같지만 유효합니다. 숫자는 저장하기 전에 부호 없는 것으로 변환됩니다.
b = 0;비--;//위와 같은 일을 한다
그 수준에서 정밀도가 정말로 필요합니까?곱셈에는 각 피연산자 크기의 두 배에 해당하는 결과가 필요할 수 있다는 것을 알고 계십니까?0xFF * 0xFF = 0xFE01, 이 경우 8비트 정수를 사용했다면 계산을 할 수 없습니다.0xFF * 0xFF * 0xFF = 0xFD02FF를 계속 곱하면 상황은 더욱 악화됩니다.
무엇을 하려고 하는가?
귀하의 응답을 확인하는 방법은 다음과 같습니다.
나는 이전에 오일러 숫자 8을 본 적이 없습니다.몇 줄의 코드만으로 문제를 해결할 수 있으므로 좋은 인터뷰 질문인 것 같습니다.
귀하의 다른 답변:
숫자...
아마도 우리는 10개의 손가락(아마도 10개의 발가락)을 가지고 있기 때문에 "10진수"로 성장할 것입니다.우리의 시계는 대부분 60진수이지만 더 혼란스럽게 만들기 위해 10진수와 혼합되었습니다.어쨌든, 10진법은 각 숫자 자리 표시자에 대해 10개의 고유 숫자 중 하나를 갖고, 해당 위치의 최대값에 도달하면 다음 위치로 넘어간다는 것을 의미합니다.이게 다 초등학교 물건이에요.
000
001
002
003
...
008
009
010
011
012
...
가장 오른쪽 숫자에 어떻게 10개의 기호(0,1,2,3,4,5,6,7,8,9)가 있고 마지막 기호에 도달하면 처음부터 다시 시작하고 왼쪽에 있는 숫자가 씩 증가하는지 확인하세요. 하나.이 규칙은 모든 기본 번호 매기기 시스템에 적용됩니다.
0과 1이라는 두 개의 기호만 있다는 점을 제외하면 밑수 2에 해당됩니다.
000
001
010
011
100
101
...
8진수의 경우에도 마찬가지지만 8개의 기호(0,1,2,3,4,5,6,7)
000
001
002
003
004
005
006
007
010
011
012
013
...
16진수 16개 기호(0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f)의 경우에도 마찬가지입니다.
000
001
002
003
004
005
006
007
008
009
00a
00b
00c
00일
00e
00f
010
011
012
013
...
나는 컴퓨터에서 다른 진수(예: 10) 대신 바이너리를 사용하는 이유에 대해 설명하려고 했습니다.결론적으로 두 가지 상태를 켜거나 끄거나 높음과 낮음으로 설정하는 것은 쉽습니다.두 가지 상태는 밑수 2의 두 기호 1과 0과 같습니다.전자 장치를 사용 가능한 전압 내에서 2개 이상의 상태로 조정하는 것은 어렵습니다. 적어도 예전에는 그랬습니다. 0V에 가깝거나 일부 작은 수의 볼트 이상으로 유지하는 것은 비교적 쉽습니다. 따라서 디지털 전자 장치는 2진법의 두 가지 상태를 사용합니다.
인간이 이진수로 처리하는 간단한 작업도 장황하고, 간단한 2학년 수학에는 여전히 1과 0이 많습니다.그래서 8진수는 3개의 비트 그룹으로 생각할 수 있게 하고 숫자 0,1,2,3,4,5,6,7과 같이 우리에게 친숙한 기호를 사용할 수 있기 때문에 인기를 얻었습니다.그러나 또 다른 2의 거듭제곱인 4개의 그룹은 인간에게 8진수보다 훨씬 더 많은 정신적 컴퓨팅 능력을 제공하며, 16진수는 역시 2의 거듭제곱인 4비트를 기반으로 합니다.전통 아랍어 기본 10에서 빌린 10에 더 많은 기호를 추가해야 했기 때문에 알파벳의 처음 6이 사용되었습니다.8진수는 거의 사용되지 않습니다. 16진수 대신 8진수를 생각하면 나이를 알 수 있습니다.(나는 16진수 세대 출신이지만 마음속으로 8진수에서 2진수, 16진수를 얻을 수 없기 때문에 16진수로 어려움을 겪는 8진수 세대 사람들과 함께 일했습니다.)
컴퓨터의 10진수는 16진수의 평균적인 인간 사고와 같습니다.컴퓨터는 10진법을 수행하지 않고(게으른 인간의 경우 bcd를 수행했습니다) 2진법을 수행합니다.컴퓨터의 십진수 1234는 실제로 0x4D2 또는 0b010011010010입니다.이는 값으로서, 1234에 다른 숫자를 더하고 싶다면 기호 1, 2, 3, 4와 아무 관련이 없는 값이 필요하다고 가정해 보겠습니다.하지만 이 답변을 stackoverflow에 게시하기 위해 우리는 ASCII를 사용하는 숫자를 사용하지 않으므로 ascii의 1234는 0x31, 0x32, 0x33, 0x34입니다. 이는 1000자리 숫자가 ascii 문자열로 제공되었다고 가정할 때 오일러 솔루션에 대해 아는 것이 중요합니다. 문제는 기본 2 문제가 아니라 기본 10 문제이기 때문에 바이너리에서 ASCII로 변환해야 합니다.
그럼 제가 질문했던 내용으로 돌아가겠습니다.숫자를 저장하는 데 4비트의 메모리가 있다고 가정해 보겠습니다. 얼마나 큰 숫자를 저장할 수 있습니까?10진법만 생각한다면 숫자가 9라고 생각할 수도 있습니다. 왜냐하면 각 저장 위치에서 가장 큰 기호를 사용하도록 훈련받았기 때문입니다. 10진수에 5개의 저장 위치가 있는 경우 99999가 가장 큰 숫자입니다.4비트로 돌아가면, 단일 비트의 가장 큰 기호는 1입니다. 해당 숫자를 각 저장 위치에 넣으면 1111(1 4개)이 됩니다.이 네 가지를 보는 것만으로도 동일한 숫자 17 8진수 또는 F 16진수의 8진수 및 16진수 버전을 마음속으로 쉽게 볼 수 있어야 합니다.십진수를 보려면 수학이 필요합니다. 이 경우에는 암기가 필요합니다. 그 숫자는 십진수 15입니다.따라서 가질 수 있는 가장 큰 4비트 숫자는 0xF 또는 9가 아닌 15입니다.8비트 숫자는 어떻습니까?0xFF 또는 255(2의 8승 빼기 1).가장 큰 16비트 숫자?65535 등
그래서 내가 몇 비트를 사용하려고 하는지 물었을 때 이것이 내가 의미하는 바입니다.이 숫자 99999를 보세요.다시 기본 10이 가장 큰 숫자라고 생각하겠지만, 컴퓨터에서는 소수점 99999가 0x1869F이고 저장하는 데 17비트의 메모리가 필요하며 저장할 수 있는 가장 큰 17비트 숫자는 0x1FFFF, 즉 131071입니다. 99999보다 조금 더 큽니다.따라서 컴퓨터에서 큰 숫자와 수학을 생각하려면 이진수(또는 16진수)를 생각해야 합니다.
원래는 여전히 오일러 문제의 일부인 곱셈을 수행하고 있었지만 제가 질문한 것은 정밀도 및 비트 저장과 관련이 있었습니다.여기에 몇 가지 기본 사항이 있습니다. 자세히 설명하지는 않겠지만 컴퓨터에서 부동 소수점 단위에 의존하는 이유를 알 수 있습니다.
10진수 15인 가장 큰 4비트 숫자 1111(이진수)을 선택합니다.가장 큰 4비트 숫자를 추가하면 15+15 = 30 = 0x1E 또는 11110 바이너리가 됩니다.따라서 두 개의 4비트 숫자를 추가하려면 답을 유지하는 데 5비트가 필요합니다.컴퓨터는 이 추가 비트에 대해 "캐리" 비트를 유지합니다.기본적으로 컴퓨터의 정수 더하기/빼기 수학 기능을 사용하면 N+1 비트를 가질 수 있습니다.따라서 32비트 컴퓨터라면 기본적으로 덧셈/뺄셈 연산에 33비트가 사용됩니다.
문제는 곱셈과 나눗셈입니다. 심지어 오늘날에도 많은 프로세서가 이를 지원하지 않습니다(그렇습니다. 많은 프로세서에는 fpu가 없고 더하기와 빼기만 할 수 있으며 때로는 곱하기도 하지만 나누는 경우는 드뭅니다.곱셈과 나눗셈은 많은 전자 장치를 사용하지만 소프트웨어에서 더하기와 빼기를 사용하여 수행할 수 있다는 점에서 절충점이 있습니다.최악의 경우 4 비트 시스템 1111 * 1111 = 11100001에 대한 최악의 경우 곱하기 때문에 4 비트 곱셈 결과를 저장하는 데 8 비트가 걸리면 4 비트 시스템이 있으면 대부분의 곱셈이 있으면 원하는 것입니다. 4 비트로 저장할 수없는 숫자가 발생합니다.그래서 당신이 64비트 정수(부호 없는 long long은 대개 64비트임)를 취하고 4번 곱하는 것을 보았을 때, 이는 답을 저장하기 위해 64*5 또는 320비트 정수가 필요하다는 것을 의미합니다. 64개의 큰 결과는 컴파일러와 컴퓨터에 따라 행복하게 수행되고 상위 비트를 잘라내어 결과의 하위 64비트를 남기고 피연산자 중 어느 것보다 쉽게 작아 보일 수 있습니다. 이것이 제가 생각했던 것입니다. 처음에는 그랬을 수도 있습니다.
부동 소수점은 과학적 표기법에 지나지 않지만 이진수에서는 과학적 표기법을 사용하여 숫자 1234와 5678을 곱하려면 1.234*10^3 곱하기 5.678*10^3을 취하고 7.007*10^6을 얻습니다.정밀도를 유지하고 더 넓은 범위의 숫자를 표현할 수 있습니다.나는 이것이 바이너리에서 어떻게 작동하는지 설명하지 않을 것입니다.하지만 원래 질문에는 작동하지 않습니다.
아, 마지막으로 질문/답변에서 제가 무엇을 하고 있었는지 명확히 할게요.이진수의 음수.덧셈과 뺄셈 및 기본 시스템 간의 관계로 인해 몇 가지 트릭을 사용할 수 있습니다.이진수를 사용하여 숫자 7(십진수)에서 1을 빼고 싶다고 가정해 보겠습니다.음, 빼기 회로 같은 것은 없습니다. 대신 음수를 추가하면 7 - 1 대신 실제로는 7 + (-1)이 됩니다. 차이가 있습니다.
0111 + ???? = 0110
7에 어떤 숫자를 더하면 6이 이진수로 나올 수 있나요?
0111 + 1111 = 0110
이진수의 음수는 "2의 보수"라고 하며, 간단히 말해서 대답은 "1을 반전하고 더하기"입니다.마이너스 1을 이진수로 어떻게 표현하나요?더하기 1 0001을 취한 다음 이를 반전시켜 1을 0으로 만들고 0을 1(1의 보수라고도 함)로 만들고 1110을 더한 다음 1을 더합니다 1111.마이너스 1은 컴퓨터(어디서나)의 특수 숫자입니다. 비트 수에 관계없이 모든 비트가 1로 표시되기 때문입니다.그러니 누군가가 이렇게 하는 것을 보면:
부호 없는 문자 a;
a = -1;
컴파일러는 먼저 -1을 보고 ...11111(바이너리)라고 생각한 다음 등호와 다른 쪽을 살펴봅니다. 아, a가 모두 1이기를 원하면 부호 있는 정수와 부호 없는 정수가 있는 것을 확인합니다. 그러나 변환은 비트를 이동하는 것이므로 위에서 a = 0xFF를 원한다고 말하고 있습니다.(8비트 부호 없는 문자로 가정)
일부 컴파일러는 부호 없는 숫자에 음수를 저장하려고 한다고 불평할 수 있습니다.다른 컴파일러는 -1을 보고 32비트 또는 요즘에는 64비트 부호 있는 정수 상수로 보고 등호를 부호 없는 8비트로 평가할 때 부호 있는 정수에 -1을 저장할 수 없다는 경고를 받게 됩니다. 또는 타입캐스트가 없는 unsigned char.하지만 이렇게 하면:
a = 0;ㅏ--;
모든 컴파일러가 그것을 좋아할 것입니다.불평하지 않고 컴파일 시간 대신 런타임에 컴퓨팅 주기를 소모합니다.
그런데 어디선가 친구가 이진수학을 연속적으로 다루는 책에 대해 이야기해 주었습니다.예를 들어 숫자를 부정하려면 일반적으로 한 가지 트릭을 뒤집어서 광고하지만 연필과 종이를 사용하면 다른 트릭을 알려줄 수도 있습니다.오른쪽부터 시작하여 처음 1까지 0을 복사한 다음 그 이후에는 반전하여 마이너스 2를 복사합니다.
0010
1110
오른쪽부터 시작하여 0을 복사한 다음 첫 번째 비트를 복사하고 왼쪽으로 갈수록 나머지 비트를 반전시킵니다.
마이너스 6
0110
1010
마이너스 4
0100
1100
아마도 덧셈과 뺄셈(글쎄, 그거 쉽죠)뿐만 아니라 곱셈과 나눗셈도 할 수 있는 요령이 있을 것 같습니다.직렬로 수행하면 동일한 alu를 사용하여 이진수로 무한히 긴 수학을 수행할 수 있습니다.이를 수행하는 방법을 알고 있다면 이를 소프트웨어로 구현할 수 있으며 큰 상수를 곱하는 원래 질문(모든 정밀도를 유지한다는 가정하에)은 모든 컴퓨터에서 사소한 것입니다.
18446744073709551496에 대한 답은 999 ... 9가 오래 길로 지정 될 때 잘린 999 ... 여러 가지 작업이 넘쳐나는 것입니다. 그것의 결정 론적이지만 효과적으로 임의의 비트 모음 일뿐입니다.
서명되지 않은 int는 시스템 단어를 나타냅니다. 오늘날이 단어는 시스템이 32 비트 또는 64 비트인지에 따라 2^32 -1 또는 2^64-1로 최대입니다. 당신은 모자를 때리고 있습니다.
Bignum 클래스를 작성하거나 'Net에서 하나를 사용해야합니다.
어쨌든이 문제를 겪고있는 이유는 무엇입니까?
숫자는 맞을 수 없습니다 unsigned long long 범위로 GMP 라이브러리를 사용하거나 문자열을 사용하여 50과 같은 숫자의 숫자를 계산하는 것처럼 큰 숫자를 나타냅니다.
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
unsigned int nd, nz;
unsigned char *ca;
unsigned int j, n=50, q, temp;
int i;
double p;
p = 0.0;
for(j = 2; j <= n; j++)
{
p += log10((double)j);
}
nd = (int)p + 1;
ca = new unsigned char[nd+1];
if (!ca)
{
cout << "Could not allocate memory!!!";
exit(0);
}
for (i = 1; (unsigned)i < nd; i++)
{
ca[i] = 0;
}
ca[0] = 1;
p = 0.0;
for (j = 2; j <= n; j++)
{
p += log10((double)j);
nz = (int)p + 1;
q = 0;
for (i = 0;(unsigned) i <= nz; i++)
{
temp = (ca[i] * j) + q;
q = (temp / 10);
ca[i] = (char)(temp % 10);
}
}
cout << "\nThe Factorial of " << n << " is: ";
for( i = nd - 1; i >= 0; i--)
{
cout << (int)ca[i];
}
// delete []ca;
return 0;
}
