Сложение двух больших чисел

313

18 апреля 2017, 09:49

Большие числа реализую как массив unsigned __int64[8]. Как реализовать операции сложения и умножения для таких чисел? Нашел пример алгоритма на сайте, но реализовать правильно не могу. Кажется, что из-за перевода в числа по основанию?

class BigInt {
public:
unsigned __int64 number[8];
const BigInt operator+(const BigInt& rv) const
{
    BigInt res;
    unsigned __int64 carry = 0, t = 0;
    for (int i = 0; i < 8; i++)
    {
        t = number[i] + rv.number[i] + carry;
        carry = t % ULLONG_MAX;
        res.number[i] = carry;
    }
    res.number[7] = t;
    return res;
}

Answer 1

Почему бы вам не отдать выполнение вычислений компилятору? Ограничьтесь хранением в массивах значений типа unsigned long - тогда с переносами все станет проще:

unsigned long long carry = 0, t = 0;
for (int i = 0; i < 8; i++)
{
    t = (unsigned long long)number[i] + (unsigned long long)rv.number[i] + carry;
    carry = t >> 32;
    res.number[i] = t&0xFFFFFFFF;
}

Если ну очень нужно работать с 64 битами - нужны специальные действия по проверке переполнения, описанные в "Алгоритмических трюках для программистов" Генри Уоррена, второе издание, стр. 52.