Веселый вызов.:)
Я предполагаю, что вам нужны целые числа произвольной длины. Я предлагаю следующий подход:
Рассмотрим двоичный характер типа «int». Подумайте о том, как использовать простые двоичные операции для эмуляции того, что делают схемы в вашем CPU, когда они добавляют вещи. В случае, если вам интереснее более подробно, подумайте о том, чтобы прочитать this wikipedia article on half-adders and full-adders. Вы будете делать что-то похожее на это, но вы можете пойти на такой низкий уровень, но, будучи ленивым, я подумал, что я просто откажусь и найду еще более простое решение.
Но прежде чем вдаваться в какие-либо алгоритмические сведения о добавлении, вычитании, умножении, давайте найдем некоторую структуру данных. Простой способ, конечно, хранить вещи в std :: vector.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector<BaseType> value_;
};
Вы могли бы хотеть рассмотреть, если вы хотите, чтобы вектор фиксированного размера, а если предварительно выделить его. Причина в том, что для различных операций вам придется пройти через каждый элемент вектора - O (n). Возможно, вам захочется узнать, насколько сложна операция, и фиксированное n делает это.
Но теперь некоторые алгоритмы работы с числами. Вы можете сделать это на логическом уровне, но мы будем использовать эту магическую мощность процессора для вычисления результатов. Но то, что мы возьмем на себя из логической иллюстрации Half- и FullAdders, это то, как она относится к переносам. В качестве примера рассмотрим, как вы бы применили оператор + =. Для каждого номера в BigInt <> :: value_ вы должны добавить их и посмотреть, приведет ли результат к какой-либо форме переноса. Мы не будем делать это по-разному, но полагаемся на природу нашего BaseType (будь то длинный или int или короткий или любой другой): он переполняется.
Несомненно, если вы добавите два числа, результат должен быть больше, чем больший из этих чисел, не так ли? Если это не так, результат переполняется.
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 :: dives, ..., но помните о переносе. :) Вы также можете реализовать умножение и деление, используя свои плюсы и минусы, но это очень медленно, потому что это будет пересчитывать результаты, которые вы уже рассчитали в предыдущих вызовах плюс и минус на каждой итерации. Есть много хороших алгоритмов для этой простой задачи, usewikipedia или в Интернете.
И, конечно же, вы должны выполнять стандартные операторы, такие как operator<< (только сдвиг каждого значения в value_ влево на п битов, начиная с value_.size()-1 ... Ох, и помните нести :), operator< - вы можете даже немного оптимизируйте здесь, сначала проверите грубое число цифр с size(). И так далее. Затем сделайте свой класс полезным, найдя std :: ostream operator<<.
Надеюсь, что этот подход поможет!
Если это упражнение по программированию, начните кодирование. Вы не можете выполнить какое-либо упражнение иначе! – 2008-11-06 16:19:37
Первое, что есть, цифры в цифрах, но думаю в терминах базы 2^32 (4 миллиарда нечетных отдельных цифр). Возможно, в наши дни даже база 2^64. Во-вторых, всегда работайте с целыми числами без знака. Вы можете сделать двойной набор для подписанных больших целых чисел самостоятельно, но если вы попытаетесь выполнить обработку переполнения и т. Д. Со значащими целыми числами, вы столкнетесь с неопределенными стандартами проблем bahaviour. – Steve314 2011-02-14 21:42:12
Что касается алгоритмов - для базовой библиотеки те, которые вы узнали в школе, примерно совпадают. – Steve314 2011-02-14 21:42:58