Advertisement
smatskevich

Seminar5

Mar 10th, 2022
842
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.81 KB | None | 0 0
  1. #include <array>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5.  
  6. typedef unsigned int uint;
  7.  
  8. template<int n>
  9. class BigUInteger {
  10.  public:
  11.   std::string toString() const {
  12.     std::string result;
  13.     result += char(last_digit_) + '0';
  14.     result += low_.toString();
  15.     return result;
  16.   }
  17.  private:
  18.   uint last_digit_ = 5;
  19.   BigUInteger<n - 1> low_;
  20. };
  21.  
  22. template<>
  23. class BigUInteger<1> {
  24.  public:
  25.   std::string toString() const {
  26.     std::string result;
  27.     result += char(digit_) + '0';
  28.     return result;
  29.   }
  30.  private:
  31.   uint digit_ = 3;
  32. };
  33.  
  34. template<int n>
  35. class BigInteger2 {
  36.  public:
  37.   std::string toString() const {
  38.     std::string unsigned_str = unsigned_part_.toString();
  39.     return is_positive_ ? unsigned_str : '-' + unsigned_str;
  40.   }
  41.  private:
  42.   bool is_positive_ = false;
  43.   BigUInteger<n> unsigned_part_;
  44. };
  45.  
  46. int main1() {
  47.   BigInteger2<4> x;
  48.   std::cout << x.toString() << std::endl;
  49.   return 0;
  50. }
  51.  
  52.  
  53. // Из семинара 4
  54. class BigInteger {
  55.  public:
  56.   std::string ToString() const;
  57.   BigInteger operator+(const BigInteger& second) const { /*STUB*/ return *this; }
  58.   BigInteger operator-(const BigInteger& second) const;
  59.   BigInteger operator*(const BigInteger& second) const;
  60.   BigInteger operator/(const BigInteger& second) const;
  61.   BigInteger operator%(const BigInteger& second) const;
  62.  
  63.   BigInteger& operator+=(const BigInteger& second);
  64.   BigInteger& operator-=(const BigInteger& second);
  65.   BigInteger& operator*=(const BigInteger& second);
  66.   BigInteger& operator/=(const BigInteger& second);
  67.   BigInteger& operator%=(const BigInteger& second);
  68.  
  69.   BigInteger operator++(int);
  70.   BigInteger& operator++();
  71.  
  72.   bool operator==(const BigInteger& second) const;
  73.   bool operator!=(const BigInteger& second) const { return !(*this == second);}
  74.  
  75.  private:
  76.   typedef std::vector<uint> Long;
  77.  
  78.   Long digits;  // Вначале младшие разряды
  79.   bool is_positive = true;  // true, если положительно или 0
  80.  
  81.   bool IsNull() const { return digits.empty(); }
  82.   static Long Sum(const Long& l, uint r);
  83.   static Long Sub(const Long& l, uint r);  // l > r
  84.   static Long ShiftLeft(const Long& l, int k);
  85.  
  86.   friend std::istream& operator>>(std::istream& stream, BigInteger& bigint);
  87. };
  88.  
  89. std::istream& operator>>(std::istream& stream, BigInteger& bigint);
  90.  
  91. std::ostream& operator<<(std::ostream& stream, const BigInteger& bigint);
  92.  
  93. BigInteger& BigInteger::operator+=(const BigInteger& second) {
  94.   *this = *this + second;
  95.   return *this;
  96.   // Или так:
  97.   // return *this = *this + second;
  98. }
  99.  
  100. // Постфиксный
  101. BigInteger BigInteger::operator++(int) {
  102.   BigInteger copy = *this;
  103.   ++*this;
  104.   return copy;
  105. }
  106.  
  107. BigInteger& BigInteger::operator++() {
  108.   if (is_positive) {
  109.     digits = Sum(digits, 1);
  110.   } else if (digits.size() == 1 && digits[0] == 1) {
  111.     digits.clear();
  112.     is_positive = true;
  113.   } else {
  114.     digits = Sub(digits, 1);
  115.   }
  116.   return *this;
  117. }
  118.  
  119. BigInteger::Long BigInteger::Sum(const Long& l, uint r) {
  120.   Long result = l;
  121.   // ... result.back() += r; + Переполнение
  122.   return result;
  123. }
  124.  
  125. BigInteger::Long BigInteger::Sub(const Long& l, uint r) {
  126.   Long result = l;
  127.   // ... result.back() -= r; + Переполнение
  128.   return result;
  129. }
  130.  
  131. // A = 100000000 * B + R
  132. // R =
  133.  
  134. // Сдвиг влево
  135. BigInteger::Long BigInteger::ShiftLeft(const Long& l, int k) {
  136.   int full = k / 32;
  137.   int part = k % 32;
  138.  
  139.   Long result(l.size() + full + 1);
  140.   for (int i = l.size() - 1; i >= 0; --i) {
  141.     // 0000111000110010  <<  6
  142.     // 000011 1000110010
  143.     result[i + full] = l[i] << part;
  144.     result[i + full + 1] += l[i] >> (32 - part);
  145.   }
  146.  
  147.   if (result.back() == 0) result.pop_back();
  148.   return result;
  149. }
  150.  
  151. int main() {
  152.   BigInteger a, b;
  153.   BigInteger c = (a += b);
  154.   return 0;
  155. }
  156.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement