Какую структуру данных я должен использовать для класса BigInt

Question

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

Я хотел представить число в виде строки, но есть большие издержки с преобразованием строки в int и обратно для добавления.Я хочу реализовать сложение, как в старшей школе, добавить соответствующий порядок и, если результат больше 10, добавить перенос в следующий заказ.

Тогда я подумал, что было бы лучше обрабатывать его как массив unsigned long long int и хранить знак, разделенный bool.При этом я боюсь размера int, поскольку стандарт C ++, насколько я знаю, гарантирует только то, что int

Существует ли какая-либо структура данных, которая подходит или лучше для этого?

Answer 1

Итак, вы хотите динамический массив целых чисел с хорошо известным размером?

Звучит так, будто vector<uint32_t> должно работать для вас.

Answer 2

На современной 64-битной платформе x86 наилучшим подходом, вероятно, является сохранение вашего bigint в виде динамически распределяемого массива беззнаковых 32-битных целых чисел, чтобы ваша арифметика могла уместиться в 64 бит. Вы можете обрабатывать свой знак отдельно, как переменную-член класса, или можете использовать арифметику с дополнением 2 (как обычно представлены signed int).

Стандартный включаемый файл C <stdint.h> определяет uint32_t и uint64_t, поэтому вы можете избежать целочисленных типов, зависящих от платформы. Или (если ваша платформа не предоставляет их), вы можете самостоятельно импровизировать и определять такие вещи - желательно в отдельном "platform_dependent.h" файле ...

Answer 3

Как вы уже узнали, вам нужно будет использовать определенные типы в вашей платформе (или язык, если у вас есть C ++ 11), которые имеют фиксированный размер. Обычная реализация большого числа использует 32-битные целые и гарантирует, что установлены только младшие 16 бит. Это позволяет вам работать с цифрами (где цифра будет [0..2 ^ 16)), а затем нормализовать результат путем применения переносов.