Задание №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.

По ссылке https://github.com/sorokin/cpp-course/tree/master/bigint можно найти:

• big_integer_testing.cpp — набор модульных тестов для проверки корректности вашей программы. Прохождение этого набора тестов является необходимым, но не достаточным условием сдачи данного задания. При необходимости, этот набор тестов будет расширяться и дополняться. Тесты реализованы с помощью библиотеки gtest (Google Test).
• gtest/ — библиотека gtest.
• big_integer.{h, cpp} — реализация класса длинного числа с использованием библиотеки GNU Multi-Precision, которая проходит приведенные тесты.

Перед тем как писать код, возможно, стоит ознакомиться с книгой Richard Brent, Paul Zimmermann — Modern Computer Arithmetic. Про деление есть замечательная статья Multiple-Length Division Revisited: A Tour of the Minefield.