如何在内存中存储任意大的整数值?

我必须存储一个大于long数据类型的最大值的整数值。 我如何在内存中存储和操作此值?

如果可能的话,请通过一个例子来说明。

考虑使用如下结构将数字存储为十进制数字序列:

struct num { int ndigits; char d[MAXDIGITS]; }; 

例如,数字123456可以初始化为

 struct num n = { 6, { 6, 5, 4, 3, 2, 1 } }; 

反转的数字顺序对于简单计算非常重要。 特别地, nd[i]的位置值是nd[i] * 10 ^ i。

现在,几个问题:

  • 你会如何在一个num添加一个?
  • 如何将一个任意的单个数字添加到num
  • 你会如何将两个num加在一起?
  • 你如何将num乘以2?
  • 你如何将一个num乘以一个数字?
  • 你如何将num乘以10?
  • 你如何将两个num相乘? 提示:做一些铅笔和纸张乘法,看看它们是如何工作的。

如果你完成这一系列的问题,你应该能够为每一步编写一个函数,并重复使用这些函数来回答后面的问题,最后得到一个非常简单MAXDIGIT优化的长(最好是MAXDIGIT数字) )整数包用于正数的加法和乘法。

其他问题:

  • 你如何概括num来表示负数和正数?
  • 你如何将一个num除以另一个数字(忽略余数)? 这比乘法更棘手,但同样,从做一些铅笔和纸张长的分裂开始,仔细考虑你做了什么。

可能的解决方案:
1)定义大到足以容纳该值的自定义整数类型。 128位整数足以容纳98474737475747374739399。
2)使用任何可用的bignum库。

我不会给你代码,但我可以提出一些建议:

  1. 尝试将值存储为字符串并转换以执行计算
  2. 尝试将值分解为表示值的一部分的多个整数
  3. 查找可能会为您处理此问题的现有库

祝好运

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 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] = '\0'; //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=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] = '\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= 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] = '\0'; //terminate string return verylong(temp); //return verylong } 

Verylong类头

 // verylong.h // class specifier for very long integer type #include  #include  //for strlen(), etc. #include  //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]='\0'; } 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 }; 

这是大学入门计算机科学课程中的一个常见问题。 主要关注领域是:a)理解如何(整数)数字存储为二进制数字,以及b)数据结构的基础知识,如果编程语言本身不提供所需的数据结构,则可以使用元数据或集合结构例如C中的struct ,C ++中的class或Pascal中的record

那么如何在计算机中存储较小的整数? 在C中,您有数据类型char, short, int, long ,它们都可以用于存储各种大小的整数。 (我将long long忽略这一讨论。)为了一般性,我们假设在给定的32位平台上,大小分别为8位,16位,32位和64位。 考虑可以表示的值(简化为无符号)。

现在,你怎么能存储一个更大的整数,它不能存储在无符号的64位长? 创建自己的大整数数据类型,由多个较小(但标准)的整数组成,这样它们代表更大的值。

我认为这应该指出你正确的方向,并使你能够写自己的作业或考试问题的答案。

  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 } 

如果仅用于显示,我建议使用c标准库中的 (对于臭名昭着的printf)或者进行一些修改。