У меня 2 строки, обе содержат только числа. Эти числа больше максимального uint64_t
.
Как я могу сложить эти 2 числа, а затем преобразовать результат в строку?
У меня 2 строки, обе содержат только числа. Эти числа больше максимального uint64_t
.
Как я могу сложить эти 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;
}
Обратите внимание, что для ясности этот код даже не пытается обрабатывать ошибки. Негативов тоже не бывает, но исправить это несложно.
Вам нужна реализация BigInt. Вы можете найти несколько разных здесь.
Какую бы реализацию BigInt вы ни выбрали, она должна иметь преобразование в строку и из строки (обычно они это делают).
Вот код вашего вопроса:
#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;
}
Если вы просто хотите обрабатывать положительные числа, не беспокоясь о том, чтобы добавить целую библиотеку 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;
}
Вы можете повысить эффективность, например, заранее зарезервировать место в целевой строке и установить для нее определенные индексы, а не вставлять, но, если вы не обрабатываете действительно массивные строки или делаете это много em > раз в секунду, я обычно предпочитаю код, который проще понять и поддерживать.
uint64_t
, добавить их и перенести дополнительные цифры к следующему добавлению. - person Lily Ballard   schedule 13.03.2013