Как вы храните произвольно большое целочисленное значение в памяти?

Question

Я должен хранить целочисленное значение, которое больше максимального значения для длинного типа данных. Как мне хранить и манипулировать этим значением в памяти?

Пожалуйста, проиллюстрируйте это на примере, если это возможно.

Answer 1

Подумайте о сохранении чисел как последовательностей десятичных цифр, используя такую ​​структуру:

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 вместе? СОВЕТ: Сделайте умножение карандаша и бумаги и посмотрите, как они работают.

Если вы проработаете эту последовательность вопросов, вы сможете написать функцию для каждого шага и повторно использовать эти функции для ответа на более поздние вопросы, и в итоге получите очень простую и неоптимизированную MAXDIGIT цифр) целочисленный пакет для сложения и умножения положительных чисел.

Другие вопросы:

• Как вы обобщаете num для представления как отрицательных, так и положительных чисел?
• Как вы делите одно num на другое (игнорируя остатки)? Это сложнее, чем умножение, но, опять же, начните с нескольких делений на карандаш и бумагу и тщательно продумайте, что вы делаете.

Answer 2

Возможные решения:
1) Определите пользовательский целочисленный тип, который является достаточно большим, чтобы содержать это значение. 128-разрядное целое число достаточно велико, чтобы вместить 98474737475747374739399.
2) Используйте любую доступную библиотеку bignum .

Answer 3

Я не дам вам код, но я могу сделать несколько предложений для подходов:

1. Попробуйте сохранить значение в виде строки символов и конвертировать для выполнения вычислений
2. Попробуйте разбить значение на несколько целых чисел, представляющих часть значения
3. Найдите существующие библиотеки, которые позаботятся об этом за вас

Удачи

Answer 4

Роберт Лафоре - Объектно-ориентированное программирование на 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
   };

Answer 5

Это распространенный вопрос на вводных курсах по информатике в университете. Основными областями внимания являются: а) понимание того, как (целые) числа хранятся в виде двоичных цифр, и б) основы структур данных, где, если язык программирования не предоставляет нужную структуру данных, вы можете использовать или структуры коллекций, такие как struct в C, class в C ++ или record в Pascal.

Так как на компьютере хранится меньшее целое число? В C у вас есть типы данных char, short, int, long, которые могут использоваться для хранения целых чисел различных размеров. (Я проигнорирую long long для этого обсуждения.) Скажем ради общности, что на данной 32-битной платформе размеры 8-битные, 16-битные, 32-битные и 64-битные соответственно. Рассмотрим значения, которые можно представить (для упрощения считать неподписанными).

Теперь, как вы могли бы хранить большее целое число, которое не может быть сохранено в 64-битной длине без знака? Создайте свой собственный большой тип данных, состоящий из нескольких меньших (но стандартных) целых чисел, так чтобы они представляли большие значения.

Я думаю, что это должно указать вам правильное направление и дать вам возможность написать собственный ответ на домашнее задание или экзаменационный вопрос.

Answer 6

C - удивительный язык, в последние несколько дней я искал ответ для хранения больших значений в C. Затем я наконец получил ответ используйте unsigned long .it может хранить значение до 18446744073709551615. Это до 20 цифр.

  #include <stdio.h>
  int main()
    {
       unsigned long x=18446744073709551615; 
       printf("%lu",x);
       return 0;
    }

Answer 7

    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 8

Если это только для отображения, я бы предложил <stdio.h> (для печально известного printf) из стандартной библиотеки c или, возможно, <string.h>, чтобы внести некоторые изменения.