API tools faq
paste
zhangsongcui

Big Integer V3

zhangsongcui
Nov 12th, 2011
470
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.88 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #include <functional>
  3. #include <iostream>
  4. #include <string>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <iterator>
  8. #include <stdexcept>
  9. #include <cstring>
  10. #include <cstdio>
  11. #include <cassert>
  12. #if defined(_MSC_VER) && _MSC_VER < 1600
  13. typedef unsigned __int32 uint32_t;
  14. typedef unsigned __int64 uint64_t;
  15. #else
  16. #include <stdint.h>
  17. #endif
  18.  
  19. struct BigInt {
  20.     typedef std::vector<uint32_t> cont_type;
  21.     typedef cont_type::iterator cont_iter;
  22.     typedef cont_type::const_iterator cont_const_iter;
  23.     typedef cont_type::reverse_iterator cont_riter;
  24.     typedef cont_type::const_reverse_iterator cont_const_riter;
  25.  
  26.     BigInt(uint32_t val = 0): data() {
  27.         if (val != 0)
  28.             data.push_back(val);
  29.     }
  30.  
  31.     BigInt(const std::string& val) throw(std::invalid_argument): data() {
  32.         char buf[16] = {};
  33.         char* p = NULL;
  34.         std::string::const_iterator it;
  35.         for (it = val.begin(); std::distance(it, val.end()) >= 9; it += 9) {
  36.             (*this) *= 1000000000;
  37.             std::memcpy(buf, &*it, 9);
  38.             uint32_t num = std::strtoul(buf, &p, 10);
  39.             if (p != buf + 9)
  40.                 throw std::invalid_argument("invalid number");
  41.             *this += num;
  42.         }
  43.         if (it == val.end())
  44.             return;
  45.         size_t d = std::distance(it, val.end());
  46.         std::memcpy(buf, &*it, d + 1);
  47.         uint32_t num = std::strtoul(buf, &p, 10);
  48.         if (p != &buf[d])
  49.             throw std::invalid_argument("invalid number");
  50.         int times = 1;
  51.         while (d--)
  52.             times *= 10;
  53.         (*this) *= times;
  54.         (*this) += num;
  55.     }
  56.  
  57.     BigInt(const std::string& val, uint32_t rdx): data() {
  58.         for (std::string::const_iterator it = val.begin(); it != val.end(); ++it) {
  59.             (*this) *= rdx;
  60.             uint32_t num = *it > '9' ? *it - '0' : *it + 9 - 'A';
  61.             (*this) += num;
  62.         }
  63.     }
  64.  
  65.     BigInt& operator +=(uint32_t val) {
  66.         if (data.empty())
  67.             data.assign(1, val);
  68.         else {
  69.             uint64_t result = (uint64_t)data.front() + val;
  70.             data.front() = (uint32_t)result;
  71.             if ( (uint32_t)(result >> (sizeof(uint32_t) * 8)) != 0 ) {
  72.                 for (cont_iter pThis = data.begin() + 1; *pThis += 1, *pThis == 0; ++pThis) {
  73.                     if (pThis == data.end()) {
  74.                         data.push_back(1);
  75.                         break;
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.         return *this;
  81.     }
  82.  
  83.     static BigInt fromHexString(const std::string& val) throw (std::invalid_argument) {
  84.         BigInt result;
  85.         char buf[16] = {};
  86.         char* p = NULL;
  87.         std::string::const_iterator it = val.begin();
  88.         if (size_t len = val.size() % 8) {
  89.             memcpy(buf, &*it, val.size() % 8);
  90.             uint32_t num = strtoul(buf, &p, 16);
  91.             if (size_t(p - buf) != len)
  92.                 throw std::invalid_argument("invalid hex number");
  93.             result.data.push_back(num);
  94.             it += len;
  95.         }
  96.         for (; it != val.end(); it += 8) {
  97.             memcpy(buf, &*it, 8);
  98.             uint32_t num = strtoul(buf, &p, 16);
  99.             if (size_t(p - buf) != 8)
  100.                 throw std::invalid_argument("invalid hex number");
  101.             result.data.push_back(num);
  102.         }
  103.  
  104.         return result;
  105.     }
  106.  
  107.     BigInt& operator +=(const BigInt& rhs) {
  108.         // It seems that it's safe when this == &rhs;
  109.         if (data.size() < rhs.data.size())
  110.             data.resize(rhs.data.size());
  111.  
  112.         uint32_t carry = 0;
  113.         cont_iter pThis = data.begin();
  114.         for (cont_const_iter pRhs = rhs.data.begin(); pRhs != rhs.data.end(); ++pRhs, ++pThis) {
  115.             uint64_t result = (uint64_t)*pThis + *pRhs + carry;
  116.             *pThis = (uint32_t)result;
  117.             carry = (uint32_t)(result >> (sizeof(uint32_t) * 8));
  118.         }
  119.         if (carry != 0) {
  120.             for (; *pThis += 1, *pThis == 0; ++pThis) {
  121.                 if (pThis == data.end()) {
  122.                     data.push_back(1);
  123.                     break;
  124.                 }
  125.             }
  126.         }
  127.         return *this;
  128.     }
  129.  
  130.     BigInt& operator *=(uint32_t val) {
  131.         if (!data.empty()) {
  132.             if (val == 0) {
  133.                 data.clear();
  134.             } else {
  135.                 uint32_t carry = 0;
  136.                 for (cont_iter pThis = data.begin(); pThis != data.end(); ++pThis) {
  137.                     uint64_t result = (uint64_t)*pThis * val + carry;
  138.                     *pThis = (uint32_t)result;
  139.                     carry = (uint32_t)(result >> (sizeof(uint32_t) * 8));
  140.                 }
  141.                 if (carry != 0)
  142.                     data.push_back(carry);
  143.             }
  144.         }
  145.         return *this;
  146.     }
  147.  
  148.     BigInt& operator *=(const BigInt& val) {
  149.         if (this == &val)
  150.             return (*this) *= BigInt(val);
  151.  
  152.         BigInt multiplier, temp;
  153.         multiplier.data.reserve(val.data.size() + data.size());
  154.         multiplier = *this;
  155.         data.clear();
  156.         data.reserve(val.data.size() + data.size());
  157.         for (cont_const_iter pThis = val.data.begin(); pThis != val.data.end(); ++pThis) {
  158.             *this += ((temp = multiplier) *= *pThis);
  159.             multiplier.data.insert(multiplier.data.begin(), 0);
  160.         }
  161.         return *this;
  162.     }
  163.  
  164.     BigInt& operator /=(uint32_t val) throw(std::invalid_argument) {
  165.         if (val == 0)
  166.             throw std::invalid_argument("Divided by zero");
  167.         uint32_t carry = 0;
  168.         for (cont_riter pThis = data.rbegin(); pThis != data.rend(); ++pThis) {
  169.             uint64_t result = *pThis + ((uint64_t)carry << (sizeof(uint32_t) * 8));
  170.             *pThis = (uint32_t)(result / val);
  171.             carry = (uint32_t)(result % val);
  172.         }
  173.         if (data.back() == 0 && data.size() != 1)
  174.             data.pop_back();
  175.         return *this;
  176.     }
  177.  
  178.     uint32_t operator %(uint32_t val) const throw(std::invalid_argument) {
  179.         if (val == 0)
  180.             throw std::invalid_argument("Divided by zero");
  181.         uint32_t carry = 0;
  182.         for (cont_const_iter pThis = data.begin(); pThis != data.end(); ++pThis) {
  183.             uint64_t result = *pThis + ((uint64_t)carry << (sizeof(uint32_t) * 8));
  184.             carry = (uint32_t)(result % val);
  185.         }
  186.         return carry;
  187.     }
  188.  
  189. #if __cplusplus >= 201103L
  190.     BigInt operator +(uint32_t val) const {
  191.         return BigInt(*this) += val;
  192.     }
  193.  
  194.     BigInt operator +(const BigInt& rhs) const {
  195.         return BigInt(*this) += rhs;
  196.     }
  197.  
  198.     BigInt&& operator +=(BigInt&& rhs) const {
  199.         return std::move(rhs += *this);
  200.     }
  201.  
  202.     BigInt operator *(uint32_t val) const {
  203.         return BigInt(*this) *= val;
  204.     }
  205.  
  206.     BigInt operator *(const BigInt& rhs) const {
  207.         return BigInt(*this) *= rhs;
  208.     }
  209.  
  210.     BigInt&& operator *(BigInt&& rhs) const {
  211.         return std::move(rhs *= *this);
  212.     }
  213. #endif
  214.  
  215.     bool operator ==(const BigInt& rhs) const {
  216.         return data == rhs.data;
  217.     }
  218.  
  219.     std::string toString() const {
  220.         BigInt rhs = *this;
  221.         if (rhs.data.empty())
  222.             return "0";
  223.  
  224.         std::string result;
  225.         char buf[16];
  226.         while (rhs.data.size() != 1) {
  227.             std::sprintf(buf, "%09u", rhs.DivButReturnMod(1000000000));
  228.             result.insert(result.begin(), &buf[0], &buf[9]);
  229.         }
  230.  
  231.         int num = std::sprintf(buf, "%u", rhs.data[0]);
  232.         result.insert(result.begin(), &buf[0], &buf[num]);
  233.         return result;
  234.     }
  235.  
  236.     std::string toHexString() const {
  237.         if (data.empty())
  238.             return "0";
  239.         char buf[16];
  240.         std::string result;
  241.         cont_const_iter it = data.begin();
  242.         std::sprintf(buf, "%X", *it);
  243.         result += buf;
  244.         for (++it; it != data.end(); ++it) {
  245.             std::sprintf(buf, "%08X", *it);
  246.             result += buf;
  247.         }
  248.         return result;
  249.     }
  250.  
  251.     std::string toString(uint32_t rdx) const {
  252.         if (data.empty())
  253.             return "0";
  254.  
  255.         BigInt rhs = *this;
  256.         std::string result;
  257.         while (rhs.data.size() != 1) {
  258.             uint32_t num = rhs.DivButReturnMod(rdx);
  259.             result.push_back(num > 9 ? num + 'A' - 9 : num + '0');
  260.         }
  261.         std::reverse(result.begin(), result.end());
  262.         return result;
  263.     }
  264.  
  265.     friend std::ostream& operator <<(std::ostream& os, const BigInt& rhs) {
  266.         return os << rhs.toString();
  267.     }
  268.  
  269.     friend std::istream& operator >>(std::istream& is, BigInt& rhs) {
  270.         std::string result;
  271.         is >> result;
  272.         try {
  273.             rhs = result;
  274.         } catch (std::invalid_argument&) {
  275.             is.setstate(std::ios_base::badbit);
  276.         }
  277.         return is;
  278.     }
  279.  
  280.     std::ostream& printData(std::ostream& os) const {
  281.         std::ios_base::fmtflags old = os.setf(std::ios_base::hex, std::ios_base::basefield);
  282.         std::copy(data.begin(), data.end(), std::ostream_iterator<int>(os, " "));
  283.         os.setf(old);
  284.         return os;
  285.     }
  286.  
  287. private:
  288.     uint32_t DivButReturnMod(uint32_t val) {
  289.         assert(val != 0);
  290.         uint32_t carry = 0;
  291.         for (cont_riter pThis = data.rbegin(); pThis != data.rend(); ++pThis) {
  292.             uint64_t result = *pThis + ((uint64_t)carry << (sizeof(uint32_t) * 8));
  293.             *pThis = (uint32_t)(result / val);
  294.             carry = (uint32_t)(result % val);
  295.         }
  296.         if (data.back() == 0)
  297.             data.pop_back();
  298.         return carry;
  299.     }
  300.  
  301.     cont_type data; // little-endian
  302. #if __cplusplus >= 201103L
  303.     template <int index, int max, char... Nums>
  304.     friend struct B;
  305. #endif
  306. };
  307.  
  308. #if __cplusplus >= 201103L
  309. namespace BIStrConvImpl
  310. {
  311.     template <int index, int i, int Sum, char... Others>
  312.     struct A;
  313.  
  314.     template <int index, int i, int Sum, char N, char... Others>
  315.     struct A<index, i, Sum, N, Others...> {
  316.         static const int times = A<index, i + 1, Sum, Others...>::times;
  317.         static const int value = A<index, i + 1, Sum, Others...>::value;
  318.     };
  319.  
  320.     template <int index, int Sum, char N, char... Others>
  321.     struct A<index, 9, Sum, N, Others...> {
  322.         static const int times = A<index - 1, 0, Sum, N, Others...>::times;
  323.         static const int value = A<index - 1, 0, Sum, N, Others...>::value;
  324.     };
  325.  
  326.     template <int i, int Sum, char N, char... Others>
  327.     struct A<0, i, Sum, N, Others...> {
  328.         static const int times = A<0, i + 1, Sum * 10 + N - '0', Others...>::times * 10;
  329.         static const int value = A<0, i + 1, Sum * 10 + N - '0', Others...>::value;
  330.     };
  331.  
  332.     template <int Sum, char N, char... Others>
  333.     struct A<0, 9, Sum, N, Others...> {
  334.         static const int times = 1;
  335.         static const int value = Sum;
  336.     };
  337.  
  338.     template <int i, int Sum>
  339.     struct A<0, i, Sum> {
  340.         static const int times = 1;
  341.         static const int value = Sum;
  342.     };
  343.  
  344.     template <int index, int max, char... Nums>
  345.     struct B {
  346.         __attribute__((always_inline)) B(BigInt& bi) {
  347.             bi *= A<index, 0, 0, Nums...>::times;
  348.             bi += A<index, 0, 0, Nums...>::value;
  349.             B<index + 1, max, Nums...> temp(bi);
  350.         }
  351.     };
  352.  
  353.     template <int max, char... Nums>
  354.     struct B<max, max, Nums...> {
  355.         B(BigInt& bi) {}
  356.     };
  357. }
  358.  
  359. template <char... Nums>
  360. BigInt operator "" _bi() {
  361.     BigInt bi;
  362.     BIStrConvImpl::B<0, sizeof... (Nums) / 9 + (sizeof... (Nums) % 9 == 0 ? 0 : 1), Nums...> temp(bi);
  363.     return bi;
  364. }
  365. #endif //cplusplus >= 201103L
  366.  
  367. int main() {
  368.     // std::cout << 12345678912345678912345_bi * 54321987654321987654321_bi << std::endl;
  369.     BigInt bi("12345678912345678912345");
  370.     bi *= BigInt("54321987654321987654321");
  371.     std::cout << bi << std::endl;
  372.     std::cout << bi.toHexString() << std::endl;
  373.     std::cout << BigInt::fromHexString("123456ABCDEF").toHexString() << std::endl;
  374.     std::cout << 1_bi * 2_bi * 3_bi * 4_bi;
  375. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!