big_integer_addition.hpp

SECTIONMath INCLUDEnoya/big_integer_addition.hpp

对 2 到 36 进制的任意长有符号整数做规范化加法。

\[ \displaystyle C = A + B \]

Complexity: Time: O(|a| + |b|). Space: O(max(|a|, |b|)) for the returned representation.

AC 记录：addition_of_big_integers, addition_of_hex_big_integers。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @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 neg = false;
  std::string_view mag;
};

inline int digit_value(char dig) {
  if ('0' <= dig && dig <= '9') {
    return dig - '0';
  }
  if ('a' <= dig && dig <= 'z') {
    return dig - 'a' + 10;
  }
  if ('A' <= dig && dig <= 'Z') {
    return dig - 'A' + 10;
  }
  return -1;
}

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::string res;
  res.reserve(std::max(a.size(), b.size()) + 1);
  int car = 0;
  std::size_t l = a.size();
  std::size_t r = b.size();
  while (l > 0 || r > 0 || car != 0) {
    int val = car;
    if (l > 0) {
      val += digit_value(a[--l]);
    }
    if (r > 0) {
      val += digit_value(b[--r]);
    }
    res.push_back(digit_character(val % bas, cap));
    car = val / bas;
  }
  std::reverse(res.begin(), res.end());
  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;
  res.reserve(a.size());
  int bor = 0;
  std::size_t l = a.size();
  std::size_t r = b.size();
  while (l > 0) {
    int val = digit_value(a[--l]) - bor;
    if (r > 0) {
      val -= digit_value(b[--r]);
    }
    if (val < 0) {
      val += bas;
      bor = 1;
    } else {
      bor = 0;
    }
    res.push_back(digit_character(val, cap));
  }
  assert(bor == 0);
  while (res.size() > 1 && res.back() == '0') {
    res.pop_back();
  }
  std::reverse(res.begin(), res.end());
  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

#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 neg = false;
  std::string_view mag;
};

inline int digit_value(char dig) {
  if ('0' <= dig && dig <= '9') {
    return dig - '0';
  }
  if ('a' <= dig && dig <= 'z') {
    return dig - 'a' + 10;
  }
  if ('A' <= dig && dig <= 'Z') {
    return dig - 'A' + 10;
  }
  return -1;
}

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::string res;
  res.reserve(std::max(a.size(), b.size()) + 1);
  int car = 0;
  std::size_t l = a.size();
  std::size_t r = b.size();
  while (l > 0 || r > 0 || car != 0) {
    int val = car;
    if (l > 0) {
      val += digit_value(a[--l]);
    }
    if (r > 0) {
      val += digit_value(b[--r]);
    }
    res.push_back(digit_character(val % bas, cap));
    car = val / bas;
  }
  std::reverse(res.begin(), res.end());
  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;
  res.reserve(a.size());
  int bor = 0;
  std::size_t l = a.size();
  std::size_t r = b.size();
  while (l > 0) {
    int val = digit_value(a[--l]) - bor;
    if (r > 0) {
      val -= digit_value(b[--r]);
    }
    if (val < 0) {
      val += bas;
      bor = 1;
    } else {
      bor = 0;
    }
    res.push_back(digit_character(val, cap));
  }
  assert(bor == 0);
  while (res.size() > 1 && res.back() == '0') {
    res.pop_back();
  }
  std::reverse(res.begin(), res.end());
  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

#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 neg = false;
  std::string_view mag;
};

inline int digit_value(char dig) {
  if ('0' <= dig && dig <= '9') {
    return dig - '0';
  }
  if ('a' <= dig && dig <= 'z') {
    return dig - 'a' + 10;
  }
  if ('A' <= dig && dig <= 'Z') {
    return dig - 'A' + 10;
  }
  return -1;
}

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::string res;
  res.reserve(std::max(a.size(), b.size()) + 1);
  int car = 0;
  std::size_t l = a.size();
  std::size_t r = b.size();
  while (l > 0 || r > 0 || car != 0) {
    int val = car;
    if (l > 0) {
      val += digit_value(a[--l]);
    }
    if (r > 0) {
      val += digit_value(b[--r]);
    }
    res.push_back(digit_character(val % bas, cap));
    car = val / bas;
  }
  std::reverse(res.begin(), res.end());
  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;
  res.reserve(a.size());
  int bor = 0;
  std::size_t l = a.size();
  std::size_t r = b.size();
  while (l > 0) {
    int val = digit_value(a[--l]) - bor;
    if (r > 0) {
      val -= digit_value(b[--r]);
    }
    if (val < 0) {
      val += bas;
      bor = 1;
    } else {
      bor = 0;
    }
    res.push_back(digit_character(val, cap));
  }
  assert(bor == 0);
  while (res.size() > 1 && res.back() == '0') {
    res.pop_back();
  }
  std::reverse(res.begin(), res.end());
  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