big_integer_addition.hpp¶
Add two arbitrarily long signed integers represented in base 2..36. The result is canonical (no leading zeroes and no negative zero).
Verified by addition_of_big_integers, addition_of_hex_big_integers.
\[
\displaystyle C = A + B
\]
Implementation¶
#ifndef NOYA_BIG_INTEGER_ADDITION_HPP
#define NOYA_BIG_INTEGER_ADDITION_HPP 1
/// @complexity Time: O(|a| + |b|).
/// Space: O(max(|a|, |b|)) for the returned representation.
#include <algorithm>
#include <cassert>
#include <string>
#include <string_view>
namespace noya {
namespace big_integer_addition_internal {
struct parsed_integer {
bool negative = false;
std::string_view magnitude;
};
inline int digit_value(char digit) {
if ('0' <= digit && digit <= '9') {
return digit - '0';
}
if ('a' <= digit && digit <= 'z') {
return digit - 'a' + 10;
}
if ('A' <= digit && digit <= 'Z') {
return digit - 'A' + 10;
}
return -1;
}
inline parsed_integer parse(std::string_view value, int base) {
assert(2 <= base && base <= 36);
assert(!value.empty());
bool negative = value.front() == '-';
if (negative || value.front() == '+') {
value.remove_prefix(1);
}
assert(!value.empty());
for (char digit : value) {
assert(0 <= digit_value(digit) && digit_value(digit) < base);
}
while (value.size() > 1 && value.front() == '0') {
value.remove_prefix(1);
}
if (value == "0") {
negative = false;
}
return {negative, value};
}
inline int compare_magnitude(std::string_view first, std::string_view second) {
if (first.size() != second.size()) {
return first.size() < second.size() ? -1 : 1;
}
for (std::size_t index = 0; index < first.size(); index++) {
int left = digit_value(first[index]);
int right = digit_value(second[index]);
if (left != right) {
return left < right ? -1 : 1;
}
}
return 0;
}
inline char digit_character(int value, bool uppercase) {
assert(0 <= value && value < 36);
if (value < 10) {
return char('0' + value);
}
return char((uppercase ? 'A' : 'a') + value - 10);
}
inline std::string add_magnitudes(std::string_view first,
std::string_view second, int base,
bool uppercase) {
std::string result;
result.reserve(std::max(first.size(), second.size()) + 1);
int carry = 0;
std::size_t left = first.size();
std::size_t right = second.size();
while (left > 0 || right > 0 || carry != 0) {
int value = carry;
if (left > 0) {
value += digit_value(first[--left]);
}
if (right > 0) {
value += digit_value(second[--right]);
}
result.push_back(digit_character(value % base, uppercase));
carry = value / base;
}
std::reverse(result.begin(), result.end());
return result;
}
// Precondition: first >= second as unsigned magnitudes.
inline std::string subtract_magnitudes(std::string_view first,
std::string_view second, int base,
bool uppercase) {
std::string result;
result.reserve(first.size());
int borrow = 0;
std::size_t left = first.size();
std::size_t right = second.size();
while (left > 0) {
int value = digit_value(first[--left]) - borrow;
if (right > 0) {
value -= digit_value(second[--right]);
}
if (value < 0) {
value += base;
borrow = 1;
} else {
borrow = 0;
}
result.push_back(digit_character(value, uppercase));
}
assert(borrow == 0);
while (result.size() > 1 && result.back() == '0') {
result.pop_back();
}
std::reverse(result.begin(), result.end());
return result;
}
} // namespace big_integer_addition_internal
/// @brief Add two arbitrarily long signed integers represented in base 2..36.
/// The result is canonical (no leading zeroes and no negative zero).
inline std::string add_big_integers(std::string_view first,
std::string_view second, int base = 10,
bool uppercase = false) {
using namespace big_integer_addition_internal;
parsed_integer left = parse(first, base);
parsed_integer right = parse(second, base);
if (left.negative == right.negative) {
std::string result =
add_magnitudes(left.magnitude, right.magnitude, base, uppercase);
if (left.negative) {
result.insert(result.begin(), '-');
}
return result;
}
int order = compare_magnitude(left.magnitude, right.magnitude);
if (order == 0) {
return "0";
}
bool negative = order > 0 ? left.negative : right.negative;
std::string result = order > 0
? subtract_magnitudes(left.magnitude, right.magnitude,
base, uppercase)
: subtract_magnitudes(right.magnitude, left.magnitude,
base, uppercase);
if (negative) {
result.insert(result.begin(), '-');
}
return result;
}
} // namespace noya
#endif // NOYA_BIG_INTEGER_ADDITION_HPP
#include <algorithm>
#include <cassert>
#include <string>
#include <string_view>
/// @complexity Time: O(|a| + |b|).
/// Space: O(max(|a|, |b|)) for the returned representation.
namespace noya {
namespace big_integer_addition_internal {
struct parsed_integer {
bool negative = false;
std::string_view magnitude;
};
inline int digit_value(char digit) {
if ('0' <= digit && digit <= '9') {
return digit - '0';
}
if ('a' <= digit && digit <= 'z') {
return digit - 'a' + 10;
}
if ('A' <= digit && digit <= 'Z') {
return digit - 'A' + 10;
}
return -1;
}
inline parsed_integer parse(std::string_view value, int base) {
assert(2 <= base && base <= 36);
assert(!value.empty());
bool negative = value.front() == '-';
if (negative || value.front() == '+') {
value.remove_prefix(1);
}
assert(!value.empty());
for (char digit : value) {
assert(0 <= digit_value(digit) && digit_value(digit) < base);
}
while (value.size() > 1 && value.front() == '0') {
value.remove_prefix(1);
}
if (value == "0") {
negative = false;
}
return {negative, value};
}
inline int compare_magnitude(std::string_view first, std::string_view second) {
if (first.size() != second.size()) {
return first.size() < second.size() ? -1 : 1;
}
for (std::size_t index = 0; index < first.size(); index++) {
int left = digit_value(first[index]);
int right = digit_value(second[index]);
if (left != right) {
return left < right ? -1 : 1;
}
}
return 0;
}
inline char digit_character(int value, bool uppercase) {
assert(0 <= value && value < 36);
if (value < 10) {
return char('0' + value);
}
return char((uppercase ? 'A' : 'a') + value - 10);
}
inline std::string add_magnitudes(std::string_view first,
std::string_view second, int base,
bool uppercase) {
std::string result;
result.reserve(std::max(first.size(), second.size()) + 1);
int carry = 0;
std::size_t left = first.size();
std::size_t right = second.size();
while (left > 0 || right > 0 || carry != 0) {
int value = carry;
if (left > 0) {
value += digit_value(first[--left]);
}
if (right > 0) {
value += digit_value(second[--right]);
}
result.push_back(digit_character(value % base, uppercase));
carry = value / base;
}
std::reverse(result.begin(), result.end());
return result;
}
// Precondition: first >= second as unsigned magnitudes.
inline std::string subtract_magnitudes(std::string_view first,
std::string_view second, int base,
bool uppercase) {
std::string result;
result.reserve(first.size());
int borrow = 0;
std::size_t left = first.size();
std::size_t right = second.size();
while (left > 0) {
int value = digit_value(first[--left]) - borrow;
if (right > 0) {
value -= digit_value(second[--right]);
}
if (value < 0) {
value += base;
borrow = 1;
} else {
borrow = 0;
}
result.push_back(digit_character(value, uppercase));
}
assert(borrow == 0);
while (result.size() > 1 && result.back() == '0') {
result.pop_back();
}
std::reverse(result.begin(), result.end());
return result;
}
} // namespace big_integer_addition_internal
/// @brief Add two arbitrarily long signed integers represented in base 2..36.
/// The result is canonical (no leading zeroes and no negative zero).
inline std::string add_big_integers(std::string_view first,
std::string_view second, int base = 10,
bool uppercase = false) {
using namespace big_integer_addition_internal;
parsed_integer left = parse(first, base);
parsed_integer right = parse(second, base);
if (left.negative == right.negative) {
std::string result =
add_magnitudes(left.magnitude, right.magnitude, base, uppercase);
if (left.negative) {
result.insert(result.begin(), '-');
}
return result;
}
int order = compare_magnitude(left.magnitude, right.magnitude);
if (order == 0) {
return "0";
}
bool negative = order > 0 ? left.negative : right.negative;
std::string result = order > 0
? subtract_magnitudes(left.magnitude, right.magnitude,
base, uppercase)
: subtract_magnitudes(right.magnitude, left.magnitude,
base, uppercase);
if (negative) {
result.insert(result.begin(), '-');
}
return result;
}
} // namespace noya