воскресенье, 18 июля 2010 г.

Длинное + длинное

[Вся длинная арифметика]

Операция сложения двух длинных чисел:

  1. BigInt operator + (const BigInt &a, const BigInt &b)
  2. {
  3.   BigInt res;
  4.   res.amount = max(a.amount,b.amount);
  5.   int r = 0;
  6.   for (int i=0;i<res.amount | r;i++)
  7.   {
  8.     res.digits[i] = a.digits[i] + b.digits[i] + r;
  9.     if (res.digits[i]>=osn)
  10.     {
  11.       res.digits[i]-=osn;
  12.       r = 1;
  13.     }
  14.     else
  15.       r = 0;
  16.   }
  17.   if (res.digits[res.amount])
  18.     res.amount++; 
  19.  
  20.   return res;
  21. }
* This source code was highlighted with Source Code Highlighter.

В данной реализации отсутствует операция взятия остатка от деления. Вместо этого используется вычитание значения основания системы счисления в строке 11.

P.S: Данная реализация появилась на основе статьи Виталия Гольдштейна с учетом оформления длинных чисел команды HotFinnKeys.

9 комментариев:

  1. Здесь в 6 строчке
    i<res.amount | r
    тоже же можно использовать логическое "ИЛИ"?

    ОтветитьУдалить
    Ответы
    1. Да, тут точно такая же логика, что и в прошлом случае http://cppalgo.blogspot.com/2010/08/blog-post_9200.html

      Удалить
  2. В 3 строчке: разве BigInt res не должен быть приравнен к a? Получается переменная которой не присвоено значение...

    ОтветитьУдалить
    Ответы
    1. В данном случае можно не присваивать. Вы не правы. Переменной присвоено значение. Для типа BigInt определен конструктор по умолчанию. В данном случае после третей строки в res будет лежать 0

      Удалить
  3. Что проверяется в 17 строчке? Не могу понять..

    ОтветитьУдалить
    Ответы
    1. Попробуйте сложить 99 и 1 с использованием этого if'a и без него

      Удалить
    2. А что делать если он с этим If 250+500 выводит -858993460750 ?

      Удалить
    3. Похоже, что у вас на промежуточных вычислениях произошло переполнение

      Удалить
  4. В 6 строке < заменил на <= и вроде бы все работает.

    ОтветитьУдалить