big_integer_addition.hpp¶
对 2 到 36 进制的任意长有符号整数做规范化加法。
\[
\displaystyle C = A + B
\]
Complexity: Time: \(O(\lvert a\rvert + \lvert b\rvert)\). Space: \(O(\max (\lvert a\rvert , \lvert b\rvert))\) for the returned representation.
AC 记录：addition_of_big_integers, addition_of_hex_big_integers。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(|a| + |b|).
/// Space: O(max(|a|, |b|)) for the returned representation.
#include <algorithm>
#include <array>
#include <cassert>
#include <string>
#include <string_view>
namespace noya {
namespace big_integer_addition_internal {
struct parsed_integer {
bool neg = false;
std::string_view mag;
};
inline int digit_value(char dig) {
static constexpr auto values = [] {
std::array<signed char, 256> a{};
a.fill(-1);
for (int i = 0; i < 10; ++i) a['0' + i] = i;
for (int i = 0; i < 26; ++i) a['a' + i] = a['A' + i] = i + 10;
return a;
}();
return values[static_cast<unsigned char>(dig)];
}
inline parsed_integer parse(std::string_view val, int bas) {
assert(2 <= bas && bas <= 36);
assert(!val.empty());
bool neg = val.front() == '-';
if (neg || val.front() == '+') {
val.remove_prefix(1);
}
assert(!val.empty());
for (char dig : val) {
assert(0 <= digit_value(dig) && digit_value(dig) < bas);
}
while (val.size() > 1 && val.front() == '0') {
val.remove_prefix(1);
}
if (val == "0") {
neg = false;
}
return {neg, val};
}
inline int compare_magnitude(std::string_view a, std::string_view b) {
if (a.size() != b.size()) {
return a.size() < b.size() ? -1 : 1;
}
for (std::size_t idx = 0; idx < a.size(); idx++) {
int l = digit_value(a[idx]);
int r = digit_value(b[idx]);
if (l != r) {
return l < r ? -1 : 1;
}
}
return 0;
}
inline char digit_character(int val, bool cap) {
assert(0 <= val && val < 36);
if (val < 10) {
return char('0' + val);
}
return char((cap ? 'A' : 'a') + val - 10);
}
inline std::string add_magnitudes(std::string_view a, std::string_view b,
int bas, bool cap) {
std::size_t n = std::max(a.size(), b.size());
std::string res;
res.reserve(n + 1);
res.resize(n, '0');
int car = 0;
std::size_t l = a.size(), r = b.size();
for (std::size_t pos = n; pos > 0; --pos) {
int val = car;
if (l) val += digit_value(a[--l]);
if (r) val += digit_value(b[--r]);
// At most two digits and one carry: val < 2*bas.
car = val >= bas;
res[pos - 1] = digit_character(val - car * bas, cap);
}
if (car) res.insert(res.begin(), '1');
return res;
}
// Precondition: a >= b as unsigned magnitudes.
inline std::string subtract_magnitudes(std::string_view a, std::string_view b,
int bas, bool cap) {
std::string res(a.size(), '0');
int bor = 0;
std::size_t r = b.size();
for (std::size_t pos = a.size(); pos > 0; --pos) {
int val = digit_value(a[pos - 1]) - bor;
if (r) val -= digit_value(b[--r]);
bor = val < 0;
res[pos - 1] = digit_character(val + bor * bas, cap);
}
assert(bor == 0);
auto first = res.find_first_not_of('0');
if (first == std::string::npos) return "0";
if (first) res.erase(0, first);
return res;
}
} // 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 a, std::string_view b,
int bas = 10, bool cap = false) {
using namespace big_integer_addition_internal;
parsed_integer l = parse(a, bas);
parsed_integer r = parse(b, bas);
if (l.neg == r.neg) {
std::string res = add_magnitudes(l.mag, r.mag, bas, cap);
if (l.neg) {
res.insert(res.begin(), '-');
}
return res;
}
int ord = compare_magnitude(l.mag, r.mag);
if (ord == 0) {
return "0";
}
bool neg = ord > 0 ? l.neg : r.neg;
std::string res = ord > 0 ? subtract_magnitudes(l.mag, r.mag, bas, cap)
: subtract_magnitudes(r.mag, l.mag, bas, cap);
if (neg) {
res.insert(res.begin(), '-');
}
return res;
}
} // namespace noya
// NOYA_BIG_INTEGER_ADDITION_HPP
#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 <array>
#include <cassert>
#include <string>
#include <string_view>
namespace noya {
namespace big_integer_addition_internal {
struct parsed_integer {
bool neg = false;
std::string_view mag;
};
inline int digit_value(char dig) {
static constexpr auto values = [] {
std::array<signed char, 256> a{};
a.fill(-1);
for (int i = 0; i < 10; ++i) a['0' + i] = i;
for (int i = 0; i < 26; ++i) a['a' + i] = a['A' + i] = i + 10;
return a;
}();
return values[static_cast<unsigned char>(dig)];
}
inline parsed_integer parse(std::string_view val, int bas) {
assert(2 <= bas && bas <= 36);
assert(!val.empty());
bool neg = val.front() == '-';
if (neg || val.front() == '+') {
val.remove_prefix(1);
}
assert(!val.empty());
for (char dig : val) {
assert(0 <= digit_value(dig) && digit_value(dig) < bas);
}
while (val.size() > 1 && val.front() == '0') {
val.remove_prefix(1);
}
if (val == "0") {
neg = false;
}
return {neg, val};
}
inline int compare_magnitude(std::string_view a, std::string_view b) {
if (a.size() != b.size()) {
return a.size() < b.size() ? -1 : 1;
}
for (std::size_t idx = 0; idx < a.size(); idx++) {
int l = digit_value(a[idx]);
int r = digit_value(b[idx]);
if (l != r) {
return l < r ? -1 : 1;
}
}
return 0;
}
inline char digit_character(int val, bool cap) {
assert(0 <= val && val < 36);
if (val < 10) {
return char('0' + val);
}
return char((cap ? 'A' : 'a') + val - 10);
}
inline std::string add_magnitudes(std::string_view a, std::string_view b,
int bas, bool cap) {
std::size_t n = std::max(a.size(), b.size());
std::string res;
res.reserve(n + 1);
res.resize(n, '0');
int car = 0;
std::size_t l = a.size(), r = b.size();
for (std::size_t pos = n; pos > 0; --pos) {
int val = car;
if (l) val += digit_value(a[--l]);
if (r) val += digit_value(b[--r]);
// At most two digits and one carry: val < 2*bas.
car = val >= bas;
res[pos - 1] = digit_character(val - car * bas, cap);
}
if (car) res.insert(res.begin(), '1');
return res;
}
// Precondition: a >= b as unsigned magnitudes.
inline std::string subtract_magnitudes(std::string_view a, std::string_view b,
int bas, bool cap) {
std::string res(a.size(), '0');
int bor = 0;
std::size_t r = b.size();
for (std::size_t pos = a.size(); pos > 0; --pos) {
int val = digit_value(a[pos - 1]) - bor;
if (r) val -= digit_value(b[--r]);
bor = val < 0;
res[pos - 1] = digit_character(val + bor * bas, cap);
}
assert(bor == 0);
auto first = res.find_first_not_of('0');
if (first == std::string::npos) return "0";
if (first) res.erase(0, first);
return res;
}
} // 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 a, std::string_view b,
int bas = 10, bool cap = false) {
using namespace big_integer_addition_internal;
parsed_integer l = parse(a, bas);
parsed_integer r = parse(b, bas);
if (l.neg == r.neg) {
std::string res = add_magnitudes(l.mag, r.mag, bas, cap);
if (l.neg) {
res.insert(res.begin(), '-');
}
return res;
}
int ord = compare_magnitude(l.mag, r.mag);
if (ord == 0) {
return "0";
}
bool neg = ord > 0 ? l.neg : r.neg;
std::string res = ord > 0 ? subtract_magnitudes(l.mag, r.mag, bas, cap)
: subtract_magnitudes(r.mag, l.mag, bas, cap);
if (neg) {
res.insert(res.begin(), '-');
}
return res;
}
} // namespace noya
#endif // NOYA_BIG_INTEGER_ADDITION_HPP
/// @complexity Time: O(|a| + |b|).
/// Space: O(max(|a|, |b|)) for the returned representation.
#include <algorithm>
#include <array>
#include <cassert>
#include <string>
#include <string_view>
namespace noya {
namespace big_integer_addition_internal {
struct parsed_integer {
bool neg = false;
std::string_view mag;
};
inline int digit_value(char dig) {
static constexpr auto values = [] {
std::array<signed char, 256> a{};
a.fill(-1);
for (int i = 0; i < 10; ++i) a['0' + i] = i;
for (int i = 0; i < 26; ++i) a['a' + i] = a['A' + i] = i + 10;
return a;
}();
return values[static_cast<unsigned char>(dig)];
}
inline parsed_integer parse(std::string_view val, int bas) {
assert(2 <= bas && bas <= 36);
assert(!val.empty());
bool neg = val.front() == '-';
if (neg || val.front() == '+') {
val.remove_prefix(1);
}
assert(!val.empty());
for (char dig : val) {
assert(0 <= digit_value(dig) && digit_value(dig) < bas);
}
while (val.size() > 1 && val.front() == '0') {
val.remove_prefix(1);
}
if (val == "0") {
neg = false;
}
return {neg, val};
}
inline int compare_magnitude(std::string_view a, std::string_view b) {
if (a.size() != b.size()) {
return a.size() < b.size() ? -1 : 1;
}
for (std::size_t idx = 0; idx < a.size(); idx++) {
int l = digit_value(a[idx]);
int r = digit_value(b[idx]);
if (l != r) {
return l < r ? -1 : 1;
}
}
return 0;
}
inline char digit_character(int val, bool cap) {
assert(0 <= val && val < 36);
if (val < 10) {
return char('0' + val);
}
return char((cap ? 'A' : 'a') + val - 10);
}
inline std::string add_magnitudes(std::string_view a, std::string_view b,
int bas, bool cap) {
std::size_t n = std::max(a.size(), b.size());
std::string res;
res.reserve(n + 1);
res.resize(n, '0');
int car = 0;
std::size_t l = a.size(), r = b.size();
for (std::size_t pos = n; pos > 0; --pos) {
int val = car;
if (l) val += digit_value(a[--l]);
if (r) val += digit_value(b[--r]);
// At most two digits and one carry: val < 2*bas.
car = val >= bas;
res[pos - 1] = digit_character(val - car * bas, cap);
}
if (car) res.insert(res.begin(), '1');
return res;
}
// Precondition: a >= b as unsigned magnitudes.
inline std::string subtract_magnitudes(std::string_view a, std::string_view b,
int bas, bool cap) {
std::string res(a.size(), '0');
int bor = 0;
std::size_t r = b.size();
for (std::size_t pos = a.size(); pos > 0; --pos) {
int val = digit_value(a[pos - 1]) - bor;
if (r) val -= digit_value(b[--r]);
bor = val < 0;
res[pos - 1] = digit_character(val + bor * bas, cap);
}
assert(bor == 0);
auto first = res.find_first_not_of('0');
if (first == std::string::npos) return "0";
if (first) res.erase(0, first);
return res;
}
} // 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 a, std::string_view b,
int bas = 10, bool cap = false) {
using namespace big_integer_addition_internal;
parsed_integer l = parse(a, bas);
parsed_integer r = parse(b, bas);
if (l.neg == r.neg) {
std::string res = add_magnitudes(l.mag, r.mag, bas, cap);
if (l.neg) {
res.insert(res.begin(), '-');
}
return res;
}
int ord = compare_magnitude(l.mag, r.mag);
if (ord == 0) {
return "0";
}
bool neg = ord > 0 ? l.neg : r.neg;
std::string res = ord > 0 ? subtract_magnitudes(l.mag, r.mag, bas, cap)
: subtract_magnitudes(r.mag, l.mag, bas, cap);
if (neg) {
res.insert(res.begin(), '-');
}
return res;
}
} // namespace noya
// NOYA_BIG_INTEGER_ADDITION_HPP