如何在内存中存储一​​个任意大的整数值？

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 
    };