c ++ строка (int) + строка (int)

У меня 2 строки, обе содержат только числа. Эти числа больше максимального uint64_t.

Как я могу сложить эти 2 числа, а затем преобразовать результат в строку?


person John Smith    schedule 13.03.2013    source источник
comment
Вы можете использовать библиотеку bignum или разрезать строки на более мелкие строки, которые помещаются в uint64_t, добавить их и перенести дополнительные цифры к следующему добавлению.   -  person Lily Ballard    schedule 13.03.2013
comment
Вам понадобится библиотека big-integer (или напишите свою). Пора погуглить!   -  person Oliver Charlesworth    schedule 13.03.2013
comment
Самый простой подход - использовать готовую библиотеку, предназначенную именно для таких вещей.   -  person ildjarn    schedule 13.03.2013
comment
Просто найдите этот вопрос: stackoverflow .com / questions / 269268 /.   -  person Gohan    schedule 13.03.2013
comment
См. Также stackoverflow.com/questions/1218149/ для объяснения арифметики произвольной точности.   -  person paxdiablo    schedule 13.03.2013


Ответы (4)


Что ж, вы можете использовать либо больший тип данных (например, библиотеку, которая имеет дело с большими целыми числами), либо вы можете быстро создать свой собственный.

Я бы посоветовал вам, если это разовое задание, выполнять длинное сложение точно так же, как вы научились бы делать в первые несколько лет в школе. Вы можете работать непосредственно с двумя строками, добавлять столбцы, выполнять «перенос» и строить еще одну строку, содержащую результат. Вы можете сделать все это без какого-либо преобразования в двоичный файл или из него.

Здесь. Ради интереса придумал для вас решение:

string Add( const string& a, const string& b )
{
    // Reserve storage for the result.
    string result;
    result.reserve( 1 + std::max(a.size(), b.size()) );

    // Column positions and carry flag.
    int apos = a.size();
    int bpos = b.size();
    int carry = 0;

    // Add columns
    while( carry > 0 || apos > 0 || bpos > 0 )
    {
        if( apos > 0 ) carry += a[--apos] - '0';
        if( bpos > 0 ) carry += b[--bpos] - '0';
        result.push_back('0' + (carry%10));
        carry /= 10;
    }

    // The result string is backwards.  Reverse and return it.
    reverse( result.begin(), result.end() );
    return result;
}

Обратите внимание, что для ясности этот код даже не пытается обрабатывать ошибки. Негативов тоже не бывает, но исправить это несложно.

person paddy    schedule 13.03.2013
comment
Хорошее использование переноса для суммы, я раньше не видел, чтобы это делалось таким образом - это приятно уменьшает размер кода. - person paxdiablo; 13.03.2013

Вам нужна реализация BigInt. Вы можете найти несколько разных здесь.

Какую бы реализацию BigInt вы ни выбрали, она должна иметь преобразование в строку и из строки (обычно они это делают).

person Jamin Grey    schedule 13.03.2013

Вот код вашего вопроса:

#include <iostream>
#include <string>
using namespace std;
string StrAdd(string a, string b) {
  string::reverse_iterator rit_a = a.rbegin();
  string::reverse_iterator rit_b = b.rbegin();
  string c;
  int val_c_adv = 0;
  while(rit_a != a.rend() && rit_b != b.rend() ) {
    int val_a_i = *rit_a - '0';
    int val_b_i = *rit_b - '0';
    int val_c_i = val_a_i + val_b_i + val_c_adv;
    if(val_c_i >= 10 ) {
      val_c_adv = 1;
      val_c_i -= 10;
    } else {
      val_c_adv = 0;
    }
    c.insert(0,1, (char)(val_c_i+'0'));
    ++rit_a;
    ++rit_b;
  }
  if(rit_a == a.rend() ) {
    while( rit_b != b.rend() ) {
      int val_b_i = *rit_b - '0';
      int val_c_i = val_b_i + val_c_adv;
      if(val_c_i >= 10 ) {
        val_c_adv = 1;
        val_c_i -= 10;
      } else {
        val_c_adv = 0;
      }
      c.insert(0, 1, (char)(val_c_i+'0'));
      ++rit_b;
    }
  } else if( rit_b == b.rend() ) {
    while( rit_a != a.rend() ) {
      int val_a_i = *rit_a - '0';
      int val_c_i = val_a_i + val_c_adv;
      if(val_c_i >= 10 ) {
        val_c_adv = 1;
        val_c_i -= 10;
      } else {
        val_c_adv = 0;
      }
      c.insert(0, 1, (char)(val_c_i+'0'));
      ++rit_a;
    }
  }
  return c;
}

int main() {
  string res, a, b;
  cout << "a=" << endl;
  cin >> a;
  cout << "b=" << endl;
  cin >> b;
  res = StrAdd(a, b);
  cout << "Result=" << res << endl;    
}
person Kun Ling    schedule 13.03.2013

Если вы просто хотите обрабатывать положительные числа, не беспокоясь о том, чтобы добавить целую библиотеку bignum, такую ​​как GMP (наряду с ее тенденцией просто прерываться при ошибках нехватки памяти, что я считаю непростительным в библиотеке общего назначения), вы можете сверните свой, что-то вроде:

static std::string add (const std::string& num1, const std::string& num2) {
    // Make num1 the wider number to simplify further code.

    int digit, idx1 = num1.length() - 1, idx2 = num2.length() - 1;
    if (idx1 < idx2) return add (num2, num1);

    // Initialise loop variables.

    int carry = 0;
    std::string res;  // reserve idx1+2 chars if you want.

    // Add digits from right until thinner number finished.

    while (idx2 >= 0) {
        digit = num1[idx1--] - '0' + num2[idx2--] - '0' + carry;
        carry = (digit > 9);
        res.insert (0, 1, (digit % 10) + '0');
    }

    // Then just process rest of wider number and any leftover carry.

    while (idx1 >= 0) {
        digit = num1[idx1--] - '0' + carry;
        carry = (digit > 9);
        res.insert (0, 1, (digit % 10) + '0');
    }
    if (carry) res.insert (0, 1, '1');

    return res;
}

Вы можете повысить эффективность, например, заранее зарезервировать место в целевой строке и установить для нее определенные индексы, а не вставлять, но, если вы не обрабатываете действительно массивные строки или делаете это много раз в секунду, я обычно предпочитаю код, который проще понять и поддерживать.

person paxdiablo    schedule 13.03.2013