big_integer

Задание №2

В данном задании необходимо написать класс для длинного знакового числа. Требования к решению следующие:

Реализация должна содержаться в классе big_integer и находиться в файле big_integer.h. Класс должен содержать:

• Конструктор по умолчанию, инициализирующий число нулем.
• Конструктор копирования, после которого исходный объект и копию можно изменять независимо.
• Конструктор от int.
• Explicit конструктор от std::string.
• Оператор присваивания.
• Операторы сравнения.
• Арифметические операции: сложение, вычитание, изменение знака (унарный минус), унарный плюс.
• Умножение, работающее за время O(nm), где n, m — длины множителей в битах.
• Деление и остаток от деления, работающие за время O(nm), где n — длина делителя в битах, а m — длина частного в битах.
• Префиксный/постфиксный инкремент/декремент. (опционально)
• Битовые операции: и, или, исключающее или, не.
• Битовые сдвиги.
• Должна существовать глобальная функция std::string to_string(big_integer const&), возвращающая строковое представление числа.

Реализация функций класса должна быть расположена в файле big_integer.cpp.

Пользоваться сторонними библиотеками длинных чисел при выполнении этого задания нельзя.

Разряды числа должны представляться 32-битными либо 64-битными числами. При этом необходимо, чтобы все биты в их представлении использовались. Например, нельзя хранить разряды как 64-битные числа, но использовать только младшие 32-бита в них.

Реализация должна использовать арифметические операции той битности, которая естественна для данного представления разрядов. Например, нельзя разбивать разряды на отдельные битики, и делать операции в системе счисления с основанием 2.

Задание №3

В данном задании необходимо реализовать класс длинного числа со small-object и copy-on-write оптимизациями.

Длинное число должно удовлетворять всем требованиям задания 2 плюс:

• Если в big_integer хранится число -2N ≤ a ≤ 2N - 1, big_integer не должен выделять динамическую память. Конкретное значение N вы можете выбрать самостоятельно, допустимыми являются любые N ≥ 30.
• Числа a < -2N и a > 2N-1 должны выделять не больше одного блока динамической памяти на каждый экземпляр big_integer.
• Конструктор копирования и оператор присваивания должны работать за O(1) и удовлетворять гарантии безопасности исключений nothrow.