1

2 つの文字列があり、どちらも数字のみを含んでいます。これらの数値は最大の より大きいですuint64_t。

これら 2 つの数値を追加して、結果を文字列に変換するにはどうすればよいですか?

4

4 に答える 4

6

より大きなデータ型 (たとえば、大きな整数を扱うライブラリ) を使用するか、独自のデータ型をすばやく作成することができます。

これが1回限りの場合は、学校の最初の数年間で学んだのとまったく同じように長い足し算を行うことをお勧めします. 2 つの文字列を直接操作し、列を追加し、「キャリー」を実行して、結果を含む別の文字列を作成できます。バイナリとの間の変換なしで、これらすべてを実行できます。

ここ。楽しみのために、私はあなたのために解決策を思いつきました：

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;
}

わかりやすくするために、このコードはエラーを処理しようとさえしていないことに注意してください。ネガにもなりませんが、それを修正するのは難しくありません。

于 2013-03-13T01:26:21.863 に答える
1

GMPのようなbignumライブラリ全体を持ち込むことを心配せずに正の数を処理したい場合（メモリ不足エラーで中止する傾向があることに加えて、汎用ライブラリでは許されないことです）、次のことができます。次のように、自分でロールします。

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;
}

ターゲット文字列に事前にスペースを予約したり、挿入するのではなく特定のインデックスを設定したりするなどの効率を追加できますが、本当に大量の文字列を処理したり、1秒間に何度も実行したりしない限り、通常は理解しやすいコードを好みます。と維持します。

于 2013-03-13T02:00:04.960 に答える
1

BigInt の実装が必要です。ここでいくつかの異なるものを見つけることができます。

どのような BigInt 実装を選択しても、文字列との間の変換が必要です (通常はそうします)。

于 2013-03-13T01:23:17.770 に答える
1

質問のコードは次のとおりです。

#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;    
}
于 2013-03-13T02:05:02.017 に答える