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

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

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

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

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

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

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

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

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

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

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

Удачи

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

Очень длинный заголовок classа

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

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

Итак, как меньшее целое хранится на компьютере? В 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 } 

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

Давайте будем гением компьютера.