如何在內存中存儲一​​個任意大的整數值？

Question

我必須存儲一個大於長數據類型最大值的整數值。我將如何存儲和操縱這個值在內存中？

請通過示例說明，如果可能的話。

Answer 1

我不會給你的代碼，但我可以做一對夫婦的建議方法採取：

1. 嘗試存儲值作爲一個字符串，並轉換爲執行計算
2. 嘗試打破值成表示值的一部分
3. 查一查，可能照顧這對現有的庫多個整數你

好運

Answer 2

可能的解決方案：
1）定義足夠大的自定義整數類型以保存該值。 128位整數足夠容納98474737475747374739399.
2）使用任何可用的bignum庫。

Answer 3

這是大學入門計算機科學課程中的一個常見問題。主要關注點是a）理解（整數）數字如何以二進制數字的形式存儲，以及b）數據結構的基礎知識，如果編程語言本身不提供所需的數據結構，則可以使用meta或如C中的struct，C++中的class或Pascal中的record。

那麼如何在計算機中存儲一個較小的整數？在C中，您有數據類型char, short, int, long，這些數據類型都可以用來存儲各種大小的整數。 （我將忽略此討論的long long）。假設爲了一般性，在給定的32位平臺上，大小分別爲8位，16位，32位和64位。考慮可以表示的值（以簡化未考慮的無符號值）。

現在，你怎麼能存儲一個較大的整數，不能存儲在一個無符號的64位長？製作您自己的大整數數據類型，由多個較小（但標準）的整數組成，以便它們代表較大的值。

我認爲這應該指向正確的方向，並使您能夠爲自己的作業或考試問題編寫自己的答案。

Answer 4

考慮使用這樣一個結構存儲數字作爲十進制數字的序列：

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

例如，數123456可以被初始化爲

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

的顛倒位順序證明對於簡單計算來說非常重要。特別地，n.d[i]的地址值是n.d[i] * 10^i。

現在，有幾個問題：

• 你會如何添加一個到一個num？
• 你會如何添加一個任意的單個數字到num？
• 你會怎麼加兩個num？
• 你如何將num乘以二？
• 你會如何乘以一位數字num？
• 您如何將num乘以10？
• 你會如何將兩個num s放在一起？提示：做一些鉛筆和紙張的乘法運算，看看它們是如何工作的。

如果你通過這個問題序列，你應該能夠爲每個步驟編寫一個函數，並重新使用這些函數來回答後面的問題，並最終得到一個非常簡單和未優化的long（好吧，高達MAXDIGIT數字）整數包用於正數的加法和乘法。

其他問題：

• 你如何概括num表示負數，以及積極的？
• 如何將一個num除以另一個（忽略餘數）？這比乘法更復雜，但是再次，通過做一些鉛筆和紙長分區開始，仔細考慮你做了什麼。

Answer 5

如果它僅用於顯示，我會建議一個<stdio.h>（臭名昭著的printf）從C標準庫或者也許<string.h>做出一些修改。

Answer 6

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 
    } 

Answer 7

LibTomMath提供在C漂亮的任意精度的整數實現，我可以把它與幾乎沒有修改放到一個iPhone項目。

Answer 8

羅伯特·拉方爾 - 在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] = '\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<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] = '\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] = '\0';      //terminate string 
    return verylong(temp);    //return verylong 
    } 

Verylong類的頭

// 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]='\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 
    };