Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <cstring>
- #include <vector>
- #include <cassert>
- #include <unordered_map>
- #include <functional>
- #define MAX(x, y) ((x) > (y) ? (x) : (y))
- struct BigUInt192
- {
- using baseType = uint16_t;
- using oversizedType = uint32_t;
- static_assert(sizeof(baseType) < sizeof(oversizedType), "");
- BigUInt192()
- {
- parts = new baseType[arraySize];
- this->erase();
- }
- BigUInt192(const BigUInt192 &original)
- : BigUInt192()
- {
- std::memcpy(parts, original.parts, sizeof(baseType) * arraySize);
- }
- template<int T>
- void fromString(const std::string &str)
- {
- // something went wrong
- }
- void erase()
- {
- std::memset(parts, 0, sizeof(baseType) * arraySize);
- }
- template<template<class> class F, class T>
- BigUInt192 applyBlock(F<T> functor) const
- {
- BigUInt192 result;
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- result.parts[i] = functor(parts[i]);
- }
- return result;
- }
- template<template<class> class F, class T>
- BigUInt192 applyBlock(const BigUInt192 &right, F<T> functor) const
- {
- BigUInt192 result;
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- result.parts[i] = functor(parts[i], right.parts[i]);
- }
- return result;
- }
- BigUInt192 shift(char way, size_t amount, bool circled) const
- {
- BigUInt192::baseType mask = 0x0;
- for (size_t i = 0; i < amount; i++) {
- mask = static_cast<BigUInt192::baseType>(mask << 1 | 1);
- }
- BigUInt192 result;
- BigUInt192::baseType last = 0;
- if (way == 0) { // <<
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- result.parts[i] = (parts[i] << amount) | last;
- last = (parts[i] >> (8 * sizeof(BigUInt192::baseType) - amount)) & mask;
- }
- } else { // >>
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- const size_t index = BigUInt192::arraySize - i - 1;
- result.parts[index] = (parts[index] >> amount);
- result.parts[index] |= last << (8 * sizeof(BigUInt192::baseType) - amount);
- last = parts[index] & mask;
- }
- }
- if (circled) {
- if (way == 0) // <<
- result.parts[0] |= last;
- else // >>
- result.parts[BigUInt192::arraySize - 1] |= last << (8 * sizeof(BigUInt192::baseType) - amount);
- }
- return result;
- }
- template<int T>
- std::string toString() const
- {
- // something went wrong
- }
- ~BigUInt192()
- {
- delete[] parts;
- }
- static const size_t bytes = 24;
- static const size_t arraySize = bytes / sizeof(baseType) + (bytes % sizeof(baseType) > 0);
- baseType *parts;
- };
- template<>
- void BigUInt192::fromString<2>(const std::string &str)
- {
- erase();
- for (auto it = str.crbegin(); it != str.crend(); it++) {
- const size_t i = static_cast<size_t>(it - str.crbegin());
- assert(*it == '0' || *it == '1');
- if (*it == '0')
- continue;
- const size_t index = i / (sizeof(BigUInt192::baseType) * 8);
- const size_t shift = i % (sizeof(BigUInt192::baseType) * 8);
- parts[index] |= (*it - '0') << shift;
- }
- }
- template<>
- void BigUInt192::fromString<16>(const std::string &str)
- {
- static const std::unordered_map<char, uint16_t> HEX = {
- {'A', 0xA},
- {'B', 0xB},
- {'C', 0xC},
- {'D', 0xD},
- {'E', 0xE},
- {'F', 0xF},
- {'a', 0xA},
- {'b', 0xB},
- {'c', 0xC},
- {'d', 0xD},
- {'e', 0xE},
- {'f', 0xF},
- };
- static_assert(sizeof(BigUInt192::baseType) >= 2, "");
- erase();
- for (auto it = str.crbegin(); it != str.crend(); it++) {
- assert((*it > '0' && *it < '9') || (HEX.find(*it) == HEX.cend()));
- const size_t i = static_cast<size_t>(it - str.crbegin());
- if (*it > 'A')
- if (*it == '0')
- continue;
- const size_t index = i / (sizeof(BigUInt192::baseType) * 8);
- const size_t shift = i % (sizeof(BigUInt192::baseType) * 8);
- parts[index] |= (*it - '0') << shift;
- }
- }
- template<>
- std::string BigUInt192::toString<2>() const
- {
- std::stringstream stream;
- bool numberStarted = false;
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- const size_t index = BigUInt192::arraySize - i - 1;
- const size_t bits = sizeof(BigUInt192::baseType) * 8;
- for (int j = 0; j < bits; j++) {
- const size_t shift = bits - j - 1;
- auto numeral = (parts[index] >> shift) & 0x1;
- if ((numeral == 0 && numberStarted) || numeral == 1)
- stream << numeral;
- if (numeral == 1 && !numberStarted)
- numberStarted = true;
- }
- }
- return stream.str();
- }
- BigUInt192 operator+(const BigUInt192 &left, const BigUInt192 &right)
- {
- BigUInt192 result;
- BigUInt192::oversizedType last = 0;
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- BigUInt192::oversizedType partSum = left.parts[i] + right.parts[i] + last;
- if (partSum >> 16 != 0) {
- last = 1; // Переносим бит из последнего разряда (17й)
- } else {
- last = 0;
- }
- result.parts[i] = static_cast<BigUInt192::baseType>(partSum);
- }
- return result;
- }
- BigUInt192 operator-(const BigUInt192 &left, const BigUInt192 &right)
- {
- BigUInt192 result;
- bool last = false;
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- const BigUInt192::oversizedType toSub = right.parts[i] + last;
- BigUInt192::oversizedType partSub;
- if (left.parts[i] >= toSub) {
- partSub = left.parts[i] - toSub;
- last = false;
- } else {
- partSub = (1 << 8 * sizeof(BigUInt192::baseType)) + left.parts[i];
- partSub -= right.parts[i];
- last = true;
- }
- result.parts[i] = static_cast<BigUInt192::baseType>(partSub);
- }
- return result;
- }
- bool operator>(const BigUInt192 &left, const BigUInt192 &right)
- {
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- const size_t index = BigUInt192::arraySize - i - 1;
- if (left.parts[index] == right.parts[index])
- continue;
- return left.parts[index] > right.parts[index];
- }
- return false;
- }
- bool operator==(const BigUInt192 &left, const BigUInt192 &right)
- {
- for (size_t i = 0; i < BigUInt192::arraySize; i++) {
- if (left.parts[i] != right.parts[i])
- return false;
- }
- return true;
- }
- bool operator!=(const BigUInt192 &left, const BigUInt192 &right)
- {
- return !(left == right);
- }
- bool operator<(const BigUInt192 &left, const BigUInt192 &right)
- {
- return !(left > right) && left != right;
- }
- bool operator<=(const BigUInt192 &left, const BigUInt192 &right)
- {
- return left < right || left == right;
- }
- bool operator>=(const BigUInt192 &left, const BigUInt192 &right)
- {
- return left > right || left == right;
- }
- BigUInt192 operator&(const BigUInt192 &left, const BigUInt192 &right)
- {
- return left.applyBlock(right, std::bit_and<>());
- }
- BigUInt192 operator|(const BigUInt192 &left, const BigUInt192 &right)
- {
- return left.applyBlock(right, std::bit_or<>());
- }
- BigUInt192 operator^(const BigUInt192 &left, const BigUInt192 &right)
- {
- return left.applyBlock(right, std::bit_xor<>());
- }
- BigUInt192 operator~(const BigUInt192 &left)
- {
- return left.applyBlock(std::bit_not<>());
- }
- BigUInt192 operator<<(const BigUInt192 &left, size_t shift)
- {
- return left.shift(0, shift, false);
- }
- BigUInt192 operator>>(const BigUInt192 &left, size_t shift)
- {
- return left.shift(1, shift, false);
- }
- BigUInt192 circledShiftL(const BigUInt192 &left, size_t shift)
- {
- return left.shift(0, shift, true);
- }
- BigUInt192 circledShiftR(const BigUInt192 &left, size_t shift)
- {
- return left.shift(1, shift, true);
- }
- std::istream &operator>>(std::istream &istream, BigUInt192 &value)
- {
- std::string s;
- istream >> s;
- std::ios_base::fmtflags base = istream.flags() & std::istream::basefield;
- switch (base) {
- case std::ios_base::dec: {
- break;
- }
- default: {
- }
- }
- value.fromString<2>(s);
- return istream;
- }
- std::ostream &operator<<(std::ostream &ostream, const BigUInt192 &value)
- {
- auto temp = ostream.flags();
- ostream << value.toString<2>();
- return ostream;
- }
- int main()
- {
- BigUInt192 b;
- BigUInt192 v;
- std::string tmp;
- std::cin >> tmp;
- v.fromString<2>(tmp);
- std::cin >> tmp;
- b.fromString<2>(tmp);
- std::cout << circledShiftR(v, 5) << std::endl;
- std::cout << circledShiftL(v, 5) << std::endl;
- std::cout << v + b << std::endl;
- std::cout << v - b << std::endl;
- std::cout << (v & b) << std::endl;
- std::cout << (v | b) << std::endl;
- std::cout << (v > b) << std::endl;
- std::cout << "Hello, World!" << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement