Как реализовать большой int в C ++

Question

Я хотел бы реализовать большой класс int в C ++ как упражнение по программированию - класс, который может обрабатывать числа, большие, чем long int. Я знаю, что уже есть несколько реализаций с открытым исходным кодом, но я бы хотел написать свою собственную. Я пытаюсь понять, что такое правильный подход.

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

Я ищу общий подход и советы, а не рабочий код.

Answer 1

Можно попробовать реализовать что-то вроде этого:

http://www.docjar.org/html/api/java/math/BigInteger.java.html

Вам понадобится только 4 бита для одной цифры 0 - 9

Таким образом, значение Int может содержать до 8 цифр каждая. Я решил использовать массив символов, поэтому я использую удвоенную память, но для меня она используется только 1 раз.

Кроме того, при хранении всех цифр в одном int это чрезмерно усложняет его и, если что-то может даже замедлить.

У меня нет никаких тестов скорости, но, глядя на java-версию BigInteger, кажется, что она выполняет очень много работы.

Для меня я делаю следующее

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

Answer 2

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

Answer 3

Мое начало было бы иметь массив целых чисел произвольного размера, используя 31 бит и 32n в качестве переполнения.

Стартовый оператор будет ADD, а затем MAKE-NEGATIVE, используя дополнение 2. После этого вычитание проходит тривиально, и как только вы добавите / sub, все остальное выполнимо.

Возможно, есть более сложные подходы. Но это был бы наивный подход со стороны цифровой логики.