C语言 如何在内存中存储任意大的整数值？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2252896/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do you store an arbitrarily large integer value in memory?
提问by yatin
I have to store an integer value that is larger than the maximum value for the long datatype. How would I store and manipulate this value in memory?
我必须存储一个大于 long 数据类型最大值的整数值。我将如何在内存中存储和操作这个值？
Please illustrate it through an example, if possible.
如果可能，请举例说明。
回答by Dale Hagglund
Think about storing a numbers as sequences of decimal digits using a struct like this:
考虑使用如下结构将数字存储为十进制数字序列：
struct num {
int ndigits;
char d[MAXDIGITS];
};
For example, the number 123456 could be initialized as
例如，数字 123456 可以初始化为
struct num n = { 6, { 6, 5, 4, 3, 2, 1 } };
The reversed digit order turns out to be important for easy calculation. In particular, the place value of n.d[i]is n.d[i]* 10^i.
事实证明，颠倒的数字顺序对于轻松计算很重要。特别是，该位值n.d[i]是n.d[i]* 10 ^我。
Now, a few questions:
现在，有几个问题：
- How would you add one to a
num? - How would you add an arbitrary single digit to a
num? - How would you add two
nums together? - How would you multiply a
numby two? - How would you multiply a
numby a single digit? - How would you multiply a
numby 10? - How would you multiply two
nums together? HINT: Do some pencil and paper multiplications and see how they work.
- 你会如何向 a 添加一个
num？ - 您如何将任意一位数字添加到 a
num？ - 你如何将两个
nums 相加？ - 你会如何将 a 乘以
num2？ - 你将如何乘以一位
num数？ - 你会如何将 a 乘以
num10？ - 你将如何将两个
nums相乘？提示：做一些铅笔和纸的乘法，看看它们是如何工作的。
If you work through this sequence of questions, you should be able to write a function for each step, and re-use those functions to answer the later questions, and end up with a very simple and unoptimized long (well, up to MAXDIGITdigits) integer package for addition and multiplication of positive numbers.
如果您解决了这一系列问题，您应该能够为每个步骤编写一个函数，并重新使用这些函数来回答后面的问题，最终得到一个非常简单且未优化的 long（好吧，最多MAXDIGIT数字）用于正数加法和乘法的整数包。
Other questions:
其他问题：
- How do you generalize
numto represent negative numbers as well as positive? - How do you divide one
numby another (ignoring remainders)? This is trickier than multiplication, but again, start by doing a few pencil and paper long divisions and think carefully about what you do.
- 你如何概括
num表示负数和正数？ - 你如何除以
num另一个（忽略余数）？这比乘法更棘手，但同样，先做一些铅笔和纸的长除法，然后仔细考虑你要做什么。
回答by SigTerm
回答by Amish Programmer
I won't give you the code, but I can make a couple of suggestions for approaches to take:
我不会给你代码，但我可以就采取的方法提出一些建议：
- Try storing the value as a character string and converting to perform calculations
- Try breaking the value up into multiple integers representing a portion of the value
- Look up existing libraries that may take care of this for you
- 尝试将值存储为字符串并转换以执行计算
- 尝试将值分解成多个整数表示值的一部分
- 查找可能会为您处理此问题的现有库
Good luck
祝你好运
回答by raymarch
Robert Lafore - Object-Oriented Programming in C++, 4th Edition :
Robert Lafore - C++ 面向对象编程，第 4 版：
// verylong.cpp
// implements very long integer type
#include "verylong.h" //header file for verylong
//--------------------------------------------------------------
void verylong::putvl() const //display verylong
{
char temp[SZ];
strcpy(temp,vlstr); //make copy
cout << strrev(temp); //reverse the copy
} //and display it
//--------------------------------------------------------------
void verylong::getvl() //get verylong from user
{
cin >> vlstr; //get string from user
vlen = strlen(vlstr); //find its length
strrev(vlstr); //reverse it
}
//--------------------------------------------------------------
verylong verylong::operator + (const verylong v) //add verylongs
{
char temp[SZ];
int j;
//find longest number
int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0; //set to 1 if sum >= 10
for(j = 0; j<maxlen; j++) //for each position
{
int d1 = (j > vlen-1) ? 0 : vlstr[j]-'0'; //get digit
int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0'; //get digit
int digitsum = d1 + d2 + carry; //add digits
if( digitsum >= 10 ) //if there's a carry,
{ digitsum -= 10; carry=1; } //decrease sum by 10,
else //set carry to 1
carry = 0; //otherwise carry is 0
temp[j] = digitsum+'0'; //insert char in string
}
if(carry==1) //if carry at end,
temp[j++] = '1'; //last digit is 1
temp[j] = '// verylong.h
// class specifier for very long integer type
#include <iostream>
#include <string.h> //for strlen(), etc.
#include <stdlib.h> //for ltoa()
using namespace std;
const int SZ = 1000;
//maximum digits in verylongs
class verylong
{
private:
char vlstr[SZ]; //verylong number, as a string
int vlen; //length of verylong string
verylong multdigit(const int) const; //prototypes for
verylong mult10(const verylong) const; //private functions
public:
verylong() : vlen(0) //no-arg constructor
{ vlstr[0]=' struct digitcontainer
{
struct digitcontainer* left;
struct digitcontainer* right;
unsigned char digit;
}
struct longinteger
{
char sign;
struct digitcontainer* firstdigit;
}
// positive number with 1000 digits
void test()
{
struct longinteger myNumber;
myNumber.sign = '+';
myNumber.firstdigit = (struct digitcontainer*)malloc( sizeof(digitcontainer) );
myNumber.firstdigit->left = NULL;
myNumber.firstdigit->right = NULL;
myNumber.firstdigit->digit = 1;
struct digitcontainer* left = myNumber.firstdigit;
for( int i=1; i<1000; i++ )
{
left->right = (struct digitcontainer*)malloc( sizeof( digitcontainer ) );
left->right->left = left;
left->right->digit = (unsigned char)i;
left = left->right;
}
left->right = NULL;
// call free for each digitcontainer you are finished using the number
}
'; }
verylong(const char s[SZ]) //one-arg constructor
{ strcpy(vlstr, s); vlen=strlen(s); } //for string
verylong(const unsigned long n) //one-arg constructor
{ //for long int
ltoa(n, vlstr, 10); //convert to string
strrev(vlstr); //reverse it
vlen=strlen(vlstr); //find length
}
void putvl() const; //display verylong
void getvl(); //get verylong from user
verylong operator + (const verylong); //add verylongs
verylong operator * (const verylong); //multiply verylongs
};
'; //terminate string
return verylong(temp); //return temp verylong
}
//--------------------------------------------------------------
verylong verylong::operator * (const verylong v) //multiply
{ //verylongs
verylong pprod; //product of one digit
verylong tempsum; //running total
for(int j=0; j<v.vlen; j++) //for each digit in arg
{
int digit = v.vlstr[j]-'0'; //get the digit
pprod = multdigit(digit); //multiply this by digit
for(int k=0; k<j; k++) //multiply result by
pprod = mult10(pprod); // power of 10
tempsum = tempsum + pprod; //add product to total
}
return tempsum; //return total of prods
}
//--------------------------------------------------------------
verylong verylong::mult10(const verylong v) const //multiply
{ //arg by 10
char temp[SZ];
for(int j=v.vlen-1; j>=0; j--) //move digits one
temp[j+1] = v.vlstr[j]; // position higher
temp[0] = '0'; //put zero on low end
temp[v.vlen+1] = ' #include <stdio.h>
int main()
{
unsigned long x=18446744073709551615;
printf("%lu",x);
return 0;
}
'; //terminate string
return verylong(temp); //return result
}
//--------------------------------------------------------------
verylong verylong::multdigit(const int d2) const
{ //multiply this verylong
char temp[SZ]; //by digit in argument
int j, carry = 0;
for(j = 0; j<vlen; j++) //for each position
{ // in this verylong
int d1 = vlstr[j]-'0'; //get digit from this
int digitprod = d1 * d2; //multiply by that digit
digitprod += carry; //add old carry
if( digitprod >= 10 ) //if there's a new carry,
{
carry = digitprod/10; //carry is high digit
digitprod -= carry*10; //result is low digit
}
else
carry = 0; //otherwise carry is 0
temp[j] = digitprod+'0'; //insert char in string
}
if(carry != 0) //if carry at end,
temp[j++] = carry+'0'; //it's last digit
temp[j] = '##代码##'; //terminate string
return verylong(temp); //return verylong
}
Verylong class header
非常长的类标题
##代码##回答by mctylr
This is a common question in introductory computer science classes at university. The primary areas of focus are a) understanding how (integer) numbers are stored as binary digits, and b) the basics of data structures, where if a programming language does not provide the desired data structure itself, you can use metaor collection structures, such as structin C, classin C++, or recordin Pascal.
这是大学计算机科学入门课程中的常见问题。主要关注领域是 a）了解（整数）数字如何存储为二进制数字，以及 b）数据结构的基础知识，如果编程语言本身不提供所需的数据结构，您可以使用元或集合结构，例如struct在 C、classC++ 或recordPascal 中。
So how is a smaller integer stored in a computer? In C, you have data types char, short, int, longthat can all be used to store integers of various sizes. (I'll ignore long longfor this discussion.) Let's say for sake of generality that on a given 32-bit platform the sizes are 8-bit, 16-bit, 32-bit, and 64-bit respectively. Consider the values that can be represented (to simplify considered unsigned).
那么一个较小的整数是如何存储在计算机中的呢？在 C 中，您拥有char, short, int, long可用于存储各种大小整数的数据类型。（我将long long在此讨论中忽略。）为了一般性，假设在给定的 32 位平台上，大小分别为 8 位、16 位、32 位和 64 位。考虑可以表示的值（以简化考虑的无符号）。
Now, how could you store a larger integer, that cannot be stored in an unsigned 64-bit long? Make your own large integer data type, comprised of multiple smaller (but standard) integers such that they represent larger values.
现在，你怎么能存储一个更大的整数，不能存储在一个无符号的 64 位长？制作您自己的大整数数据类型，由多个较小（但标准）的整数组成，以便它们表示较大的值。
I think this should point you in the right direction, and enable you to write your own answer to your homework or exam question.
我认为这应该为您指明正确的方向，并使您能够为您的家庭作业或考试问题写出自己的答案。
回答by Holger Kretzschmar
回答by call me Steve
If it's only for display, I would suggest a <stdio.h>(for the infamous printf) from the c standard library or maybe the <string.h>to make some modification.
如果仅用于显示，我会建议使用<stdio.h>c 标准库中的（对于臭名昭著的 printf），或者<string.h>进行一些修改。
回答by Ayush Kapri
C is an amazing language ,from last few days i was searching for the answer to store large values in C .then i finally got a answer. use unsigned long .it can typically store value up to 18446744073709551615. It's up to 20 digit number.
C 是一种了不起的语言，从最近几天开始，我一直在寻找在 C 中存储大值的答案。然后我终于得到了答案。使用 unsigned long 。它通常可以存储最多 18446744073709551615 的值。最多 20 位数字。
##代码##