如何在内存中存储任意大的整数值?
我必须存储一个大于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库。
我不会给你代码,但我可以提出一些建议:
- 尝试将值存储为字符串并转换以执行计算
- 尝试将值分解为表示值的一部分的多个整数
- 查找可能会为您处理此问题的现有库
祝好运
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)或者
进行一些修改。