Как эффективно хранить большое число в массиве целых чисел?C ++ - PullRequest
Новая
       17

Как эффективно хранить большое число в массиве целых чисел?C ++

0 голосов
/ 18 мая 2018

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

Это представление в памяти числа

335897294593872

вот так 

int number[] = {3, 3, 5, 8, 9, 7, 2, 9, 4, 5, 9, 3, 8, 7, 2};

недопустимо,

, ни 

char number[] = {3, 3, 5, 8, 9, 7, 2, 9, 4, 5, 9, 3, 8, 7, 2};

, ни 

std::string number("335897294593872");

Что я хочу сделать, это разделитьцелое число делится на 32-битные чанки и хранит каждый отдельный чанк в отдельном элементе массива, тип данных которого равен u32int_t.

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

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

Заранее спасибо.

РЕДАКТИРОВАТЬ: Использование только стандартных библиотек C ++

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

Ответы [ 3 ]

0 голосов
/ 18 мая 2018

Обычно, когда вы работаете с деньгами или такими деликатными числами, вы часто используете целые числа, потому что вы можете убедиться в этом во многих вещах, поэтому я рекомендую, чтобы, когда вы работаете с этими большими числами, имитировали фиксированную точку или плавающуюТочечная арифметика с двумя Ints, так что вы можете «наблюдать» за тем, как все выполняется, вы можете проверить стандарт IEEE 754 для плавающей запятой.Если вы храните число в массиве, убедитесь, что вы делаете постоянное количество шагов, чтобы выполнить все операции, которые вы выполняете, манипулируя им.Что может быть сложно.

Я рекомендую вам доверять целым числам, но фиксировать размер битов.Но если вы действительно хотите заниматься интересными вещами, попробуйте использовать побитовые операторы, и, возможно, вы могли бы получить что-то интересное, если это так.

Вы можете проверить детали типов данных здесь , в частности, signed short int или long long int, и чтобы подтвердить размеры типов данных, проверьте this

0 голосов
/ 23 мая 2018

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

Я обычно не рекомендую использовать long long целочисленные версии для ячеек массива, так каккак правило, они не имеют собственного размера архитектуры, поэтому, чтобы дать архитектуре некоторый шанс сделать что-либо эффективно, я должен использовать сокращенный (по крайней мере, один бит, чтобы иметь возможность увидеть выполнения от одного расширенная цифра к следующему) стандарт unsigned (например, gnu ** libgmp * использует 24-битные целые числа в каждой ячейке массива - в прошлый раз, когда я проверял это).Также распространено уменьшать его до кратного char размера, поэтому смещения и перераспределение чисел проще, чем 31 bit смещения для полного массива битов.

0 голосов
/ 18 мая 2018

Это довольно наивное решение:

  1. Если последняя цифра в строке нечетная, сохраните результат 1 (иначе оставьте 0).
  2. Разделите цифры в строке на 2(с учетом переносов).
  3. Если записано 32 бита, добавьте еще один элемент к результирующему вектору.
  4. Повторяйте это до тех пор, пока строка не будет содержать только 0.

Исходный код: 

#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<uint32_t> toBigInt(std::string text)
{
  // convert string to BCD-like
  for (char &c : text) c -= '0';
  // build result vector
  std::vector<uint32_t> value(1, 0);
  uint32_t bit = 1;
  for (;;) {
    // set next bit if last digit is odd
    if (text.back() & 1) value.back() |= bit;
    // divide BCD-like by 2
    bool notNull = false; int carry = 0;
    for (char &c : text) {
      const int carryNew = c & 1;
      c /= 2; c += carry * 5;
      carry = carryNew;
      notNull |= c;
    }
    if (!notNull) break;
    // shift bit
    bit <<= 1;
    if (!bit) {
      value.push_back(0); bit = 1;
    }
  }
  // done
  return value;
}

std::ostream& operator<<(std::ostream &out, const std::vector<uint32_t> &value)
{
  std::ios fmtOld(0); fmtOld.copyfmt(out);
  for (size_t i = value.size(); i--;) {
    out << std::hex << value[i] << std::setfill('0') << std::setw(sizeof (uint32_t) * 2);
  }
  out.copyfmt(fmtOld);
  return out;
}

int main()
{
  std::string tests[] = {
    "0", "1",
    "4294967295", // 0xffffffff
    "4294967296", // 0x100000000
    "18446744073709551615", // 0xffffffffffffff
    "18446744073709551616", // 0x100000000000000
  };
  for (const std::string &test : tests) {
    std::cout << test << ": " << toBigInt(test) << '\n';
  }
  return 0;
}

Выход: 

0: 0
1: 1
4294967295: ffffffff
4294967296: 100000000
18446744073709551615: ffffffffffffffff
18446744073709551616: 10000000000000000

Живая демоверсия на coliru

Примечания:

  1. Выходные данные имеют порядок байтов.(Наименее значимый элемент - первый.)
  2. Для tests я использовал числа, в которых шестнадцатеричный код легко проверить на глаз.
...