Веселое испытание. :)
Я предполагаю, что вы хотите целые числа произвольной длины. Я предлагаю следующий подход:
Рассмотрим двоичную природу типа данных "int". Подумайте об использовании простых двоичных операций, чтобы эмулировать действия схем в вашем процессоре, когда они что-то добавляют. Если вы заинтересованы в более глубоком изучении, прочитайте эту статью в Википедии о полусуммерах и полных сумматорах . Вы будете делать что-то похожее на это, но вы можете понизиться до такого низкого уровня - но, будучи ленивым, я подумал, что просто воздержусь и найду еще более простое решение.
Но прежде чем углубляться в алгоритмические подробности о сложении, вычитании, умножении, давайте найдем некоторую структуру данных. Конечно, простой способ хранить вещи в std :: vector.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};
Возможно, вы захотите подумать, хотите ли вы сделать вектор фиксированного размера и предварительно его выделить. Причина в том, что для разнообразных операций вам придется пройти через каждый элемент вектора - O (n). Возможно, вы захотите узнать, насколько сложной будет операция, и фиксированное n делает именно это.
Но теперь о некоторых алгоритмах работы с числами. Вы можете сделать это на логическом уровне, но мы будем использовать эту магическую мощность процессора для вычисления результатов. Но то, что мы извлечем из логической иллюстрации Half- и FullAdders, - это то, как они работают с переносами. В качестве примера рассмотрим, как можно реализовать оператор + = . Для каждого числа в BigInt <> :: value_ вы добавите их и посмотрите, не приведет ли результат к какой-либо форме переноса. Мы не будем делать это побитно, но будем полагаться на природу нашего BaseType (будь то long или int, short или что-то еще): он переполнен.
Конечно, если вы добавите два числа, результат должен быть больше, чем большее из этих чисел, верно? Если это не так, то результат переполнен.
template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
}
else carry = 0;
}
return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
// not, then you must restrict BaseType to be the second biggest type
// available, i.e. a 32-bit int when you have a 64-bit long. Then use
// a temporary or a cast to the mightier type and retrieve the upper bits.
// Or you do it bitwise. ;-)
Другая арифметическая операция выполняется аналогично. Черт возьми, вы можете даже использовать stl-функторы std :: plus и std :: minus, std :: times и std :: divides, ..., но помните о переносе. :) Вы также можете реализовать умножение и деление, используя операторы «плюс» и «минус», но это очень медленно, потому что это пересчитало бы результаты, которые вы уже рассчитывали в предыдущих вызовах плюс и минус в каждой итерации. Есть много хороших алгоритмов для этой простой задачи: использовать википедию или Интернет.
И, конечно, вы должны реализовать стандартные операторы, такие как operator<< (просто сдвиньте каждое значение в value_ влево для n битов, начиная с value_.size()-1 ... oh и запомните перенос :), operator< - здесь вы можете даже немного оптимизировать, сначала проверяя приблизительное количество цифр с помощью size(). И так далее. Тогда сделайте ваш класс полезным, используя befriendig std :: ostream operator<<.
Надеюсь, что этот подход полезен!