В данном задании необходимо написать класс для длинного знакового числа. Требования к решению следующие:
Реализация должна содержаться в классе 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.
В данном задании необходимо реализовать класс длинного числа со 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.