boost/multiprecision/cpp_int.hpp

   1 //////////////////3/////////////////////////////////////////////
   2 //  Copyright 2012 John Maddock. Distributed under the Boost
   3 //  Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   5
   6 #ifndef BOOST_MP_CPP_INT_HPP
   7 #define BOOST_MP_CPP_INT_HPP
   8
   9 #include <iostream>
  10 #include <iomanip>
  11 #include <boost/cstdint.hpp>
  12 #include <boost/multiprecision/number.hpp>
  13 #include <boost/multiprecision/detail/integer_ops.hpp>
  14 #include <boost/multiprecision/detail/rebind.hpp>
  15 #include <boost/core/empty_value.hpp>
  16 #include <boost/array.hpp>
  17 #include <boost/type_traits/is_integral.hpp>
  18 #include <boost/type_traits/is_floating_point.hpp>
  19 #include <boost/multiprecision/cpp_int/cpp_int_config.hpp>
  20 #include <boost/multiprecision/rational_adaptor.hpp>
  21 #include <boost/multiprecision/traits/is_byte_container.hpp>
  22 #include <boost/predef/other/endian.h>
  23 #include <boost/integer/static_min_max.hpp>
  24 #include <boost/type_traits/common_type.hpp>
  25 #include <boost/type_traits/make_signed.hpp>
  26 #include <boost/multiprecision/cpp_int/checked.hpp>
  27 #include <boost/multiprecision/detail/constexpr.hpp>
  28 #ifdef BOOST_MP_USER_DEFINED_LITERALS
  29 #include <boost/multiprecision/cpp_int/value_pack.hpp>
  30 #endif
  31
  32 namespace boost {
  33 namespace multiprecision {
  34 namespace backends {
  35
  36 using boost::enable_if;
  37
  38 #ifdef BOOST_MSVC
  39 #pragma warning(push)
  40 #pragma warning(disable : 4307) // integral constant overflow (oveflow is in a branch not taken when it would overflow)
  41 #pragma warning(disable : 4127) // conditional expression is constant
  42 #pragma warning(disable : 4702) // Unreachable code (reachability depends on template params)
  43 #endif
  44
  45 template <unsigned MinBits = 0, unsigned MaxBits = 0, boost::multiprecision::cpp_integer_type SignType = signed_magnitude, cpp_int_check_type Checked = unchecked, class Allocator = typename mpl::if_c<MinBits && (MinBits == MaxBits), void, std::allocator<limb_type> >::type>
  46 struct cpp_int_backend;
  47
  48 } // namespace backends
  49
  50 namespace detail {
  51
  52 template <unsigned MinBits, unsigned MaxBits, boost::multiprecision::cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
  53 struct is_byte_container<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> > : public boost::false_type
  54 {};
  55
  56 } // namespace detail
  57
  58 namespace backends {
  59
  60 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, bool trivial = false>
  61 struct cpp_int_base;
  62 //
  63 // Traits class determines the maximum and minimum precision values:
  64 //
  65 template <class T>
  66 struct max_precision;
  67
  68 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
  69 struct max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
  70 {
  71    static const unsigned value = is_void<Allocator>::value ? static_unsigned_max<MinBits, MaxBits>::value
  72                                                            : (((MaxBits >= MinBits) && MaxBits) ? MaxBits : UINT_MAX);
  73 };
  74
  75 template <class T>
  76 struct min_precision;
  77
  78 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
  79 struct min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
  80 {
  81    static const unsigned value = (is_void<Allocator>::value ? static_unsigned_max<MinBits, MaxBits>::value : MinBits);
  82 };
  83 //
  84 // Traits class determines whether the number of bits precision requested could fit in a native type,
  85 // we call this a "trivial" cpp_int:
  86 //
  87 template <class T>
  88 struct is_trivial_cpp_int
  89 {
  90    static const bool value = false;
  91 };
  92
  93 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
  94 struct is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
  95 {
  96    typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> self;
  97    static const bool                                                       value = is_void<Allocator>::value && (max_precision<self>::value <= (sizeof(double_limb_type) * CHAR_BIT) - (SignType == signed_packed ? 1 : 0));
  98 };
  99
 100 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
 101 struct is_trivial_cpp_int<cpp_int_base<MinBits, MaxBits, SignType, Checked, Allocator, true> >
 102 {
 103    static const bool value = true;
 104 };
 105
 106 } // namespace backends
 107 //
 108 // Traits class to determine whether a cpp_int_backend is signed or not:
 109 //
 110 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
 111 struct is_unsigned_number<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
 112     : public mpl::bool_<(SignType == unsigned_magnitude) || (SignType == unsigned_packed)>
 113 {};
 114
 115 namespace backends {
 116 //
 117 // Traits class determines whether T should be implicitly convertible to U, or
 118 // whether the constructor should be made explicit.  The latter happens if we
 119 // are losing the sign, or have fewer digits precision in the target type:
 120 //
 121 template <class T, class U>
 122 struct is_implicit_cpp_int_conversion;
 123
 124 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
 125 struct is_implicit_cpp_int_conversion<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >
 126 {
 127    typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>      t1;
 128    typedef cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t2;
 129    static const bool                                                            value =
 130        (is_signed_number<t2>::value || !is_signed_number<t1>::value) && (max_precision<t1>::value <= max_precision<t2>::value);
 131 };
 132
 133 //
 134 // Traits class to determine whether operations on a cpp_int may throw:
 135 //
 136 template <class T>
 137 struct is_non_throwing_cpp_int : public mpl::false_
 138 {};
 139 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType>
 140 struct is_non_throwing_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, unchecked, void> > : public mpl::true_
 141 {};
 142
 143 //
 144 // Traits class, determines whether the cpp_int is fixed precision or not:
 145 //
 146 template <class T>
 147 struct is_fixed_precision;
 148 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
 149 struct is_fixed_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
 150     : public mpl::bool_<max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value != UINT_MAX>
 151 {};
 152
 153 namespace detail {
 154
 155 inline BOOST_MP_CXX14_CONSTEXPR void verify_new_size(unsigned new_size, unsigned min_size, const mpl::int_<checked>&)
 156 {
 157    if (new_size < min_size)
 158       BOOST_THROW_EXCEPTION(std::overflow_error("Unable to allocate sufficient storage for the value of the result: value overflows the maximum allowable magnitude."));
 159 }
 160 inline BOOST_MP_CXX14_CONSTEXPR void verify_new_size(unsigned /*new_size*/, unsigned /*min_size*/, const mpl::int_<unchecked>&) {}
 161
 162 template <class U>
 163 inline BOOST_MP_CXX14_CONSTEXPR void verify_limb_mask(bool b, U limb, U mask, const mpl::int_<checked>&)
 164 {
 165    // When we mask out "limb" with "mask", do we loose bits?  If so it's an overflow error:
 166    if (b && (limb & ~mask))
 167       BOOST_THROW_EXCEPTION(std::overflow_error("Overflow in cpp_int arithmetic: there is insufficient precision in the target type to hold all of the bits of the result."));
 168 }
 169 template <class U>
 170 inline BOOST_MP_CXX14_CONSTEXPR void verify_limb_mask(bool /*b*/, U /*limb*/, U /*mask*/, const mpl::int_<unchecked>&) {}
 171
 172 } // namespace detail
 173
 174 //
 175 // Now define the various data layouts that are possible as partial specializations of the base class,
 176 // starting with the default arbitrary precision signed integer type:
 177 //
 178 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 179 struct cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>
 180     : private boost::empty_value<typename detail::rebind<limb_type, Allocator>::type>
 181 {
 182    typedef typename detail::rebind<limb_type, Allocator>::type allocator_type;
 183 #ifdef BOOST_NO_CXX11_ALLOCATOR
 184    typedef typename allocator_type::pointer       limb_pointer;
 185    typedef typename allocator_type::const_pointer const_limb_pointer;
 186 #else
 187    typedef typename std::allocator_traits<allocator_type>::pointer       limb_pointer;
 188    typedef typename std::allocator_traits<allocator_type>::const_pointer const_limb_pointer;
 189 #endif
 190    typedef mpl::int_<Checked> checked_type;
 191
 192    //
 193    // Interface invariants:
 194    //
 195    BOOST_STATIC_ASSERT(!is_void<Allocator>::value);
 196
 197  private:
 198    typedef boost::empty_value<allocator_type> base_type;
 199
 200    struct limb_data
 201    {
 202       unsigned     capacity;
 203       limb_pointer data;
 204    };
 205
 206  public:
 207    BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
 208    BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
 209    BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = static_cast<limb_type>(1u) << (limb_bits - 1));
 210    BOOST_STATIC_CONSTANT(unsigned, internal_limb_count =
 211       MinBits
 212          ? (MinBits / limb_bits + ((MinBits % limb_bits) ? 1 : 0))
 213          : (sizeof(limb_data) / sizeof(limb_type)) > 1 ? (sizeof(limb_data) / sizeof(limb_type)) : 2);
 214    BOOST_STATIC_CONSTANT(bool, variable = true);
 215
 216  private:
 217    union data_type
 218    {
 219       limb_data        ld;
 220       limb_type        la[internal_limb_count];
 221       limb_type        first;
 222       double_limb_type double_first;
 223
 224       BOOST_CONSTEXPR data_type() : first(0) {}
 225       BOOST_CONSTEXPR data_type(limb_type i) : first(i) {}
 226       BOOST_CONSTEXPR data_type(signed_limb_type i) : first(i < 0 ? static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(i)) : i) {}
 227 #if BOOST_ENDIAN_LITTLE_BYTE
 228       BOOST_CONSTEXPR data_type(double_limb_type i) : double_first(i)
 229       {}
 230       BOOST_CONSTEXPR data_type(signed_double_limb_type i) : double_first(i < 0 ? static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i)) : i) {}
 231 #endif
 232    };
 233
 234    data_type m_data;
 235    unsigned  m_limbs;
 236    bool      m_sign, m_internal;
 237
 238  public:
 239    //
 240    // Direct construction:
 241    //
 242    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i) BOOST_NOEXCEPT
 243        : m_data(i),
 244          m_limbs(1),
 245          m_sign(false),
 246          m_internal(true) {}
 247    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_limb_type i) BOOST_NOEXCEPT
 248        : m_data(i),
 249          m_limbs(1),
 250          m_sign(i < 0),
 251          m_internal(true) {}
 252 #if BOOST_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
 253    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i) BOOST_NOEXCEPT
 254        : m_data(i),
 255          m_limbs(i > max_limb_value ? 2 : 1),
 256          m_sign(false),
 257          m_internal(true)
 258    {}
 259    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_double_limb_type i) BOOST_NOEXCEPT
 260        : m_data(i),
 261          m_limbs(i < 0 ? (static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i)) > static_cast<double_limb_type>(max_limb_value) ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
 262          m_sign(i < 0),
 263          m_internal(true) {}
 264 #endif
 265    //
 266    // Helper functions for getting at our internal data, and manipulating storage:
 267    //
 268    BOOST_MP_FORCEINLINE allocator_type& allocator() BOOST_NOEXCEPT { return base_type::get(); }
 269    BOOST_MP_FORCEINLINE const allocator_type& allocator() const BOOST_NOEXCEPT { return base_type::get(); }
 270    BOOST_MP_FORCEINLINE unsigned              size() const BOOST_NOEXCEPT { return m_limbs; }
 271    BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return m_internal ? m_data.la : m_data.ld.data; }
 272    BOOST_MP_FORCEINLINE const_limb_pointer limbs() const BOOST_NOEXCEPT { return m_internal ? m_data.la : m_data.ld.data; }
 273    BOOST_MP_FORCEINLINE unsigned           capacity() const BOOST_NOEXCEPT { return m_internal ? internal_limb_count : m_data.ld.capacity; }
 274    BOOST_MP_FORCEINLINE bool               sign() const BOOST_NOEXCEPT { return m_sign; }
 275    void                                    sign(bool b) BOOST_NOEXCEPT
 276    {
 277       m_sign = b;
 278       // Check for zero value:
 279       if (m_sign && (m_limbs == 1))
 280       {
 281          if (limbs()[0] == 0)
 282             m_sign = false;
 283       }
 284    }
 285    void resize(unsigned new_size, unsigned min_size)
 286    {
 287       static const unsigned max_limbs = MaxBits / (CHAR_BIT * sizeof(limb_type)) + ((MaxBits % (CHAR_BIT * sizeof(limb_type))) ? 1 : 0);
 288       // We never resize beyond MaxSize:
 289       if (new_size > max_limbs)
 290          new_size = max_limbs;
 291       detail::verify_new_size(new_size, min_size, checked_type());
 292       // See if we have enough capacity already:
 293       unsigned cap = capacity();
 294       if (new_size > cap)
 295       {
 296          // Allocate a new buffer and copy everything over:
 297          cap             = (std::min)((std::max)(cap * 4, new_size), max_limbs);
 298          limb_pointer pl = allocator().allocate(cap);
 299          std::memcpy(pl, limbs(), size() * sizeof(limbs()[0]));
 300          if (!m_internal)
 301             allocator().deallocate(limbs(), capacity());
 302          else
 303             m_internal = false;
 304          m_limbs            = new_size;
 305          m_data.ld.capacity = cap;
 306          m_data.ld.data     = pl;
 307       }
 308       else
 309       {
 310          m_limbs = new_size;
 311       }
 312    }
 313    BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT
 314    {
 315       limb_pointer p = limbs();
 316       while ((m_limbs - 1) && !p[m_limbs - 1])
 317          --m_limbs;
 318    }
 319    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT : m_data(), m_limbs(1), m_sign(false), m_internal(true) {}
 320    BOOST_MP_FORCEINLINE                 cpp_int_base(const cpp_int_base& o) : base_type(o), m_limbs(0), m_internal(true)
 321    {
 322       resize(o.size(), o.size());
 323       std::memcpy(limbs(), o.limbs(), o.size() * sizeof(limbs()[0]));
 324       m_sign = o.m_sign;
 325    }
 326 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 327    cpp_int_base(cpp_int_base&& o)
 328        : base_type(static_cast<base_type&&>(o)), m_limbs(o.m_limbs), m_sign(o.m_sign), m_internal(o.m_internal)
 329    {
 330       if (m_internal)
 331       {
 332          std::memcpy(limbs(), o.limbs(), o.size() * sizeof(limbs()[0]));
 333       }
 334       else
 335       {
 336          m_data.ld    = o.m_data.ld;
 337          o.m_limbs    = 0;
 338          o.m_internal = true;
 339       }
 340    }
 341    cpp_int_base& operator=(cpp_int_base&& o) BOOST_NOEXCEPT
 342    {
 343       if (!m_internal)
 344          allocator().deallocate(m_data.ld.data, m_data.ld.capacity);
 345       *static_cast<base_type*>(this) = static_cast<base_type&&>(o);
 346       m_limbs                        = o.m_limbs;
 347       m_sign                         = o.m_sign;
 348       m_internal                     = o.m_internal;
 349       if (m_internal)
 350       {
 351          std::memcpy(limbs(), o.limbs(), o.size() * sizeof(limbs()[0]));
 352       }
 353       else
 354       {
 355          m_data.ld    = o.m_data.ld;
 356          o.m_limbs    = 0;
 357          o.m_internal = true;
 358       }
 359       return *this;
 360    }
 361 #endif
 362    BOOST_MP_FORCEINLINE ~cpp_int_base() BOOST_NOEXCEPT
 363    {
 364       if (!m_internal)
 365          allocator().deallocate(limbs(), capacity());
 366    }
 367    void assign(const cpp_int_base& o)
 368    {
 369       if (this != &o)
 370       {
 371          static_cast<base_type&>(*this) = static_cast<const base_type&>(o);
 372          m_limbs                        = 0;
 373          resize(o.size(), o.size());
 374          std::memcpy(limbs(), o.limbs(), o.size() * sizeof(limbs()[0]));
 375          m_sign = o.m_sign;
 376       }
 377    }
 378    BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
 379    {
 380       m_sign = !m_sign;
 381       // Check for zero value:
 382       if (m_sign && (m_limbs == 1))
 383       {
 384          if (limbs()[0] == 0)
 385             m_sign = false;
 386       }
 387    }
 388    BOOST_MP_FORCEINLINE bool isneg() const BOOST_NOEXCEPT
 389    {
 390       return m_sign;
 391    }
 392    BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
 393    {
 394       std::swap(m_data, o.m_data);
 395       std::swap(m_sign, o.m_sign);
 396       std::swap(m_internal, o.m_internal);
 397       std::swap(m_limbs, o.m_limbs);
 398    }
 399
 400  protected:
 401    template <class A>
 402    void check_in_range(const A&) BOOST_NOEXCEPT {}
 403 };
 404
 405 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 406
 407 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 408 const unsigned cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::limb_bits;
 409 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 410 const limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::max_limb_value;
 411 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 412 const limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::sign_bit_mask;
 413 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 414 const unsigned cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::internal_limb_count;
 415 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 416 const bool cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::variable;
 417
 418 #endif
 419
 420 template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
 421 struct cpp_int_base<MinBits, MaxBits, unsigned_magnitude, Checked, Allocator, false>
 422     : private boost::empty_value<typename detail::rebind<limb_type, Allocator>::type>
 423 {
 424    //
 425    // There is currently no support for unsigned arbitrary precision arithmetic, largely
 426    // because it's not clear what subtraction should do:
 427    //
 428    BOOST_STATIC_ASSERT_MSG(((sizeof(Allocator) == 0) && !is_void<Allocator>::value), "There is curently no support for unsigned arbitrary precision integers.");
 429 };
 430 //
 431 // Fixed precision (i.e. no allocator), signed-magnitude type with limb-usage count:
 432 //
 433 template <unsigned MinBits, cpp_int_check_type Checked>
 434 struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>
 435 {
 436    typedef limb_type*         limb_pointer;
 437    typedef const limb_type*   const_limb_pointer;
 438    typedef mpl::int_<Checked> checked_type;
 439
 440    //
 441    // Interface invariants:
 442    //
 443    BOOST_STATIC_ASSERT_MSG(MinBits > sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
 444
 445  public:
 446    BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
 447    BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
 448    BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = static_cast<limb_type>(1u) << (limb_bits - 1));
 449    BOOST_STATIC_CONSTANT(unsigned, internal_limb_count = MinBits / limb_bits + ((MinBits % limb_bits) ? 1 : 0));
 450    BOOST_STATIC_CONSTANT(bool, variable = false);
 451    BOOST_STATIC_CONSTANT(limb_type, upper_limb_mask = (MinBits % limb_bits) ? (limb_type(1) << (MinBits % limb_bits)) - 1 : (~limb_type(0)));
 452    BOOST_STATIC_ASSERT_MSG(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");
 453
 454  private:
 455    union data_type
 456    {
 457       limb_type        m_data[internal_limb_count];
 458       limb_type        m_first_limb;
 459       double_limb_type m_double_first_limb;
 460
 461       BOOST_CONSTEXPR data_type()
 462 #if defined(BOOST_NO_CXX11_UNIFIED_INITIALIZATION_SYNTAX) || defined(BOOST_NO_CXX14_CONSTEXPR)
 463          : m_first_limb(0) {}
 464 #else
 465          : m_data{ 0 } {}
 466 #endif
 467       BOOST_CONSTEXPR data_type(limb_type i)
 468 #if defined(BOOST_NO_CXX11_UNIFIED_INITIALIZATION_SYNTAX) || defined(BOOST_NO_CXX14_CONSTEXPR)
 469          : m_first_limb(i) {}
 470 #else
 471          : m_data{ i } {}
 472 #endif
 473 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 474       BOOST_CONSTEXPR data_type(limb_type i, limb_type j) : m_data{ i, j } {}
 475 #endif
 476       BOOST_CONSTEXPR data_type(double_limb_type i) : m_double_first_limb(i)
 477       {
 478 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 479          if (BOOST_MP_IS_CONST_EVALUATED(m_double_first_limb))
 480          {
 481             data_type t(static_cast<limb_type>(i & max_limb_value), static_cast<limb_type>(i >> limb_bits));
 482             *this = t;
 483          }
 484 #endif
 485       }
 486 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
 487       template <limb_type... VALUES>
 488       BOOST_CONSTEXPR data_type(literals::detail::value_pack<VALUES...>) : m_data{VALUES...}
 489       {}
 490 #endif
 491    } m_wrapper;
 492    boost::uint16_t m_limbs;
 493    bool            m_sign;
 494
 495  public:
 496    //
 497    // Direct construction:
 498    //
 499    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i) BOOST_NOEXCEPT
 500        : m_wrapper(i),
 501          m_limbs(1),
 502          m_sign(false) {}
 503    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_limb_type i) BOOST_NOEXCEPT
 504        : m_wrapper(limb_type(i < 0 ? static_cast<limb_type>(-static_cast<signed_double_limb_type>(i)) : i)),
 505          m_limbs(1),
 506          m_sign(i < 0) {}
 507 #if BOOST_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
 508    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i) BOOST_NOEXCEPT
 509        : m_wrapper(i),
 510          m_limbs(i > max_limb_value ? 2 : 1),
 511          m_sign(false)
 512    {}
 513    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_double_limb_type i) BOOST_NOEXCEPT
 514        : m_wrapper(double_limb_type(i < 0 ? static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i)) : i)),
 515          m_limbs(i < 0 ? (static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i)) > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
 516          m_sign(i < 0) {}
 517 #endif
 518 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
 519    template <limb_type... VALUES>
 520    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<VALUES...> i)
 521        : m_wrapper(i), m_limbs(sizeof...(VALUES)), m_sign(false)
 522    {}
 523    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<> i)
 524        : m_wrapper(i), m_limbs(1), m_sign(false) {}
 525    BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& a, const literals::detail::negate_tag&)
 526        : m_wrapper(a.m_wrapper), m_limbs(a.m_limbs), m_sign((a.m_limbs == 1) && (*a.limbs() == 0) ? false : !a.m_sign) {}
 527 #endif
 528 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 529    //
 530    // These are deprecated in C++20 unless we make them explicit:
 531    //
 532    constexpr cpp_int_base& operator=(const cpp_int_base&) = default;
 533 #endif
 534    //
 535    // Helper functions for getting at our internal data, and manipulating storage:
 536    //
 537    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size() const BOOST_NOEXCEPT { return m_limbs; }
 538    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() BOOST_NOEXCEPT { return m_wrapper.m_data; }
 539    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs() const BOOST_NOEXCEPT { return m_wrapper.m_data; }
 540    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign() const BOOST_NOEXCEPT { return m_sign; }
 541    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) BOOST_NOEXCEPT
 542    {
 543       m_sign = b;
 544       // Check for zero value:
 545       if (m_sign && (m_limbs == 1))
 546       {
 547          if (limbs()[0] == 0)
 548             m_sign = false;
 549       }
 550    }
 551    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(unsigned new_size, unsigned min_size) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 552    {
 553       m_limbs = static_cast<boost::uint16_t>((std::min)(new_size, internal_limb_count));
 554       detail::verify_new_size(m_limbs, min_size, checked_type());
 555    }
 556    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 557    {
 558       limb_pointer p = limbs();
 559       detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count - 1], upper_limb_mask, checked_type());
 560       p[internal_limb_count - 1] &= upper_limb_mask;
 561       while ((m_limbs - 1) && !p[m_limbs - 1])
 562          --m_limbs;
 563       if ((m_limbs == 1) && (!*p))
 564          m_sign = false; // zero is always unsigned
 565    }
 566
 567    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT : m_wrapper(limb_type(0u)), m_limbs(1), m_sign(false) {}
 568    // Not defaulted, it breaks constexpr support in the Intel compiler for some reason:
 569    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
 570        : m_wrapper(o.m_wrapper),
 571          m_limbs(o.m_limbs),
 572          m_sign(o.m_sign) {}
 573    // Defaulted functions:
 574    //~cpp_int_base() BOOST_NOEXCEPT {}
 575
 576    void BOOST_MP_CXX14_CONSTEXPR assign(const cpp_int_base& o) BOOST_NOEXCEPT
 577    {
 578       if (this != &o)
 579       {
 580          m_limbs = o.m_limbs;
 581 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 582          if (BOOST_MP_IS_CONST_EVALUATED(m_limbs))
 583          {
 584             for (unsigned i = 0; i < m_limbs; ++i)
 585                limbs()[i] = o.limbs()[i];
 586          }
 587          else
 588 #endif
 589             std::memcpy(limbs(), o.limbs(), o.size() * sizeof(o.limbs()[0]));
 590          m_sign = o.m_sign;
 591       }
 592    }
 593    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void negate() BOOST_NOEXCEPT
 594    {
 595       m_sign = !m_sign;
 596       // Check for zero value:
 597       if (m_sign && (m_limbs == 1))
 598       {
 599          if (limbs()[0] == 0)
 600             m_sign = false;
 601       }
 602    }
 603    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR bool isneg() const BOOST_NOEXCEPT
 604    {
 605       return m_sign;
 606    }
 607    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
 608    {
 609       for (unsigned i = 0; i < (std::max)(size(), o.size()); ++i)
 610          std_constexpr::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
 611       std_constexpr::swap(m_sign, o.m_sign);
 612       std_constexpr::swap(m_limbs, o.m_limbs);
 613    }
 614
 615  protected:
 616    template <class A>
 617    BOOST_MP_CXX14_CONSTEXPR void check_in_range(const A&) BOOST_NOEXCEPT {}
 618 };
 619 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 620
 621 template <unsigned MinBits, cpp_int_check_type Checked>
 622 const unsigned cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::limb_bits;
 623 template <unsigned MinBits, cpp_int_check_type Checked>
 624 const limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::max_limb_value;
 625 template <unsigned MinBits, cpp_int_check_type Checked>
 626 const limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::sign_bit_mask;
 627 template <unsigned MinBits, cpp_int_check_type Checked>
 628 const unsigned cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::internal_limb_count;
 629 template <unsigned MinBits, cpp_int_check_type Checked>
 630 const bool cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::variable;
 631
 632 #endif
 633 //
 634 // Fixed precision (i.e. no allocator), unsigned type with limb-usage count:
 635 //
 636 template <unsigned MinBits, cpp_int_check_type Checked>
 637 struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>
 638 {
 639    typedef limb_type*         limb_pointer;
 640    typedef const limb_type*   const_limb_pointer;
 641    typedef mpl::int_<Checked> checked_type;
 642
 643    //
 644    // Interface invariants:
 645    //
 646    BOOST_STATIC_ASSERT_MSG(MinBits > sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
 647
 648  public:
 649    BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
 650    BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
 651    BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = static_cast<limb_type>(1u) << (limb_bits - 1));
 652    BOOST_STATIC_CONSTANT(unsigned, internal_limb_count = MinBits / limb_bits + ((MinBits % limb_bits) ? 1 : 0));
 653    BOOST_STATIC_CONSTANT(bool, variable = false);
 654    BOOST_STATIC_CONSTANT(limb_type, upper_limb_mask = (MinBits % limb_bits) ? (limb_type(1) << (MinBits % limb_bits)) - 1 : (~limb_type(0)));
 655    BOOST_STATIC_ASSERT_MSG(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");
 656
 657  private:
 658    union data_type
 659    {
 660       limb_type        m_data[internal_limb_count];
 661       limb_type        m_first_limb;
 662       double_limb_type m_double_first_limb;
 663
 664       BOOST_CONSTEXPR data_type()
 665 #if defined(BOOST_NO_CXX11_UNIFIED_INITIALIZATION_SYNTAX) || defined(BOOST_NO_CXX14_CONSTEXPR)
 666          : m_first_limb(0) {}
 667 #else
 668          : m_data{ 0 } {}
 669 #endif
 670       BOOST_CONSTEXPR data_type(limb_type i)
 671 #if defined(BOOST_NO_CXX11_UNIFIED_INITIALIZATION_SYNTAX) || defined(BOOST_NO_CXX14_CONSTEXPR)
 672          : m_first_limb(i) {}
 673 #else
 674          : m_data{ i } {}
 675 #endif
 676 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 677       BOOST_CONSTEXPR data_type(limb_type i, limb_type j) : m_data { i, j } {}
 678 #endif
 679       BOOST_CONSTEXPR data_type(double_limb_type i) : m_double_first_limb(i)
 680       {
 681 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 682          if (BOOST_MP_IS_CONST_EVALUATED(m_double_first_limb))
 683          {
 684             data_type t(static_cast<limb_type>(i & max_limb_value), static_cast<limb_type>(i >> limb_bits));
 685             *this = t;
 686          }
 687 #endif
 688       }
 689 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
 690       template <limb_type... VALUES>
 691       BOOST_CONSTEXPR data_type(literals::detail::value_pack<VALUES...>) : m_data{VALUES...}
 692       {}
 693 #endif
 694    } m_wrapper;
 695    limb_type m_limbs;
 696
 697  public:
 698    //
 699    // Direct construction:
 700    //
 701    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i) BOOST_NOEXCEPT
 702        : m_wrapper(i),
 703          m_limbs(1) {}
 704    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(signed_limb_type i) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 705        : m_wrapper(limb_type(i < 0 ? static_cast<limb_type>(-static_cast<signed_double_limb_type>(i)) : i)), m_limbs(1)
 706    {
 707       if (i < 0)
 708          negate();
 709    }
 710 #if BOOST_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
 711    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i) BOOST_NOEXCEPT
 712        : m_wrapper(i),
 713          m_limbs(i > max_limb_value ? 2 : 1)
 714    {}
 715    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(signed_double_limb_type i) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 716        : m_wrapper(double_limb_type(i < 0 ? static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i)) : i)),
 717          m_limbs(i < 0 ? (static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i)) > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1))
 718    {
 719       if (i < 0)
 720          negate();
 721    }
 722 #endif
 723 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
 724    template <limb_type... VALUES>
 725    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<VALUES...> i)
 726        : m_wrapper(i), m_limbs(sizeof...(VALUES))
 727    {}
 728    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<>)
 729        : m_wrapper(static_cast<limb_type>(0u)), m_limbs(1) {}
 730 #endif
 731    //
 732    // Helper functions for getting at our internal data, and manipulating storage:
 733    //
 734    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size() const BOOST_NOEXCEPT { return m_limbs; }
 735    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() BOOST_NOEXCEPT { return m_wrapper.m_data; }
 736    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs() const BOOST_NOEXCEPT { return m_wrapper.m_data; }
 737    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign() const BOOST_NOEXCEPT { return false; }
 738    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 739    {
 740       if (b)
 741          negate();
 742    }
 743    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(unsigned new_size, unsigned min_size) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 744    {
 745       m_limbs = (std::min)(new_size, internal_limb_count);
 746       detail::verify_new_size(m_limbs, min_size, checked_type());
 747    }
 748    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 749    {
 750       limb_pointer p = limbs();
 751       detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count - 1], upper_limb_mask, checked_type());
 752       p[internal_limb_count - 1] &= upper_limb_mask;
 753       while ((m_limbs - 1) && !p[m_limbs - 1])
 754          --m_limbs;
 755    }
 756
 757    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT
 758        : m_wrapper(limb_type(0u)),
 759          m_limbs(1) {}
 760    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
 761        : m_wrapper(o.m_wrapper),
 762          m_limbs(o.m_limbs) {}
 763    // Defaulted functions:
 764    //~cpp_int_base() BOOST_NOEXCEPT {}
 765 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 766    //
 767    // These are deprecated in C++20 unless we make them explicit:
 768    //
 769    constexpr cpp_int_base& operator=(const cpp_int_base&) = default;
 770 #endif
 771
 772    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void assign(const cpp_int_base& o) BOOST_NOEXCEPT
 773    {
 774       if (this != &o)
 775       {
 776          m_limbs = o.m_limbs;
 777 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 778          if (BOOST_MP_IS_CONST_EVALUATED(m_limbs))
 779          {
 780             for (unsigned i = 0; i < m_limbs; ++i)
 781                limbs()[i] = o.limbs()[i];
 782          }
 783          else
 784 #endif
 785             std::memcpy(limbs(), o.limbs(), o.size() * sizeof(limbs()[0]));
 786       }
 787    }
 788
 789  private:
 790    void check_negate(const mpl::int_<checked>&)
 791    {
 792       BOOST_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned number."));
 793    }
 794    BOOST_MP_CXX14_CONSTEXPR void check_negate(const mpl::int_<unchecked>&) {}
 795
 796  public:
 797    BOOST_MP_CXX14_CONSTEXPR void negate() BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 798    {
 799       // Not so much a negate as a complement - this gets called when subtraction
 800       // would result in a "negative" number:
 801       if ((m_limbs == 1) && (m_wrapper.m_data[0] == 0))
 802          return; // negating zero is always zero, and always OK.
 803       check_negate(checked_type());
 804       unsigned i = m_limbs;
 805       for (; i < internal_limb_count; ++i)
 806          m_wrapper.m_data[i] = 0;
 807       m_limbs = internal_limb_count;
 808       for (i = 0; i < internal_limb_count; ++i)
 809          m_wrapper.m_data[i] = ~m_wrapper.m_data[i];
 810       normalize();
 811       eval_increment(static_cast<cpp_int_backend<MinBits, MinBits, unsigned_magnitude, Checked, void>&>(*this));
 812    }
 813    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool isneg() const BOOST_NOEXCEPT
 814    {
 815       return false;
 816    }
 817    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
 818    {
 819       for (unsigned i = 0; i < (std::max)(size(), o.size()); ++i)
 820          std_constexpr::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
 821       std_constexpr::swap(m_limbs, o.m_limbs);
 822    }
 823
 824  protected:
 825    template <class A>
 826    BOOST_MP_CXX14_CONSTEXPR void check_in_range(const A&) BOOST_NOEXCEPT {}
 827 };
 828 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 829
 830 template <unsigned MinBits, cpp_int_check_type Checked>
 831 const unsigned cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::limb_bits;
 832 template <unsigned MinBits, cpp_int_check_type Checked>
 833 const limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::max_limb_value;
 834 template <unsigned MinBits, cpp_int_check_type Checked>
 835 const limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::sign_bit_mask;
 836 template <unsigned MinBits, cpp_int_check_type Checked>
 837 const unsigned cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::internal_limb_count;
 838 template <unsigned MinBits, cpp_int_check_type Checked>
 839 const bool cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::variable;
 840
 841 #endif
 842 //
 843 // Traits classes to figure out a native type with N bits, these vary from boost::uint_t<N> only
 844 // because some platforms have native integer types longer than boost::long_long_type, "really boost::long_long_type" anyone??
 845 //
 846 template <unsigned N, bool s>
 847 struct trivial_limb_type_imp
 848 {
 849    typedef double_limb_type type;
 850 };
 851
 852 template <unsigned N>
 853 struct trivial_limb_type_imp<N, true>
 854 {
 855    typedef typename boost::uint_t<N>::least type;
 856 };
 857
 858 template <unsigned N>
 859 struct trivial_limb_type : public trivial_limb_type_imp<N, N <= sizeof(boost::long_long_type) * CHAR_BIT>
 860 {};
 861 //
 862 // Backend for fixed precision signed-magnitude type which will fit entirely inside a "double_limb_type":
 863 //
 864 template <unsigned MinBits, cpp_int_check_type Checked>
 865 struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, true>
 866 {
 867    typedef typename trivial_limb_type<MinBits>::type local_limb_type;
 868    typedef local_limb_type*                          limb_pointer;
 869    typedef const local_limb_type*                    const_limb_pointer;
 870    typedef mpl::int_<Checked>                        checked_type;
 871
 872  protected:
 873    BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(local_limb_type) * CHAR_BIT);
 874    BOOST_STATIC_CONSTANT(local_limb_type, limb_mask = (MinBits < limb_bits) ? local_limb_type((local_limb_type(~local_limb_type(0))) >> (limb_bits - MinBits)) : local_limb_type(~local_limb_type(0)));
 875
 876  private:
 877    local_limb_type m_data;
 878    bool            m_sign;
 879
 880    //
 881    // Interface invariants:
 882    //
 883    BOOST_STATIC_ASSERT_MSG(MinBits <= sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
 884
 885  protected:
 886    template <class T>
 887    BOOST_MP_CXX14_CONSTEXPR typename boost::disable_if_c<!boost::is_integral<T>::value || (std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits))>::type
 888    check_in_range(T val, const mpl::int_<checked>&)
 889    {
 890       typedef typename common_type<typename make_unsigned<T>::type, local_limb_type>::type common_type;
 891
 892       if (static_cast<common_type>(boost::multiprecision::detail::unsigned_abs(val)) > static_cast<common_type>(limb_mask))
 893          BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
 894    }
 895    template <class T>
 896    BOOST_MP_CXX14_CONSTEXPR typename boost::disable_if_c<boost::is_integral<T>::value || (std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits))>::type
 897    check_in_range(T val, const mpl::int_<checked>&)
 898    {
 899       using std::abs;
 900       typedef typename common_type<T, local_limb_type>::type common_type;
 901
 902       if (static_cast<common_type>(abs(val)) > static_cast<common_type>(limb_mask))
 903          BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
 904    }
 905    template <class T, int C>
 906    BOOST_MP_CXX14_CONSTEXPR void check_in_range(T, const mpl::int_<C>&) BOOST_NOEXCEPT {}
 907
 908    template <class T>
 909    BOOST_MP_CXX14_CONSTEXPR void check_in_range(T val) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<T>(), checked_type())))
 910    {
 911       check_in_range(val, checked_type());
 912    }
 913
 914  public:
 915    //
 916    // Direct construction:
 917    //
 918    template <class SI>
 919    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == unchecked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
 920        : m_data(i < 0 ? static_cast<local_limb_type>(static_cast<typename make_unsigned<SI>::type>(boost::multiprecision::detail::unsigned_abs(i)) & limb_mask) : static_cast<local_limb_type>(i & limb_mask)), m_sign(i < 0) {}
 921    template <class SI>
 922    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == checked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
 923        : m_data(i < 0 ? (static_cast<local_limb_type>(static_cast<typename make_unsigned<SI>::type>(boost::multiprecision::detail::unsigned_abs(i)) & limb_mask)) : static_cast<local_limb_type>(i & limb_mask)), m_sign(i < 0)
 924    {
 925       check_in_range(i);
 926    }
 927    template <class UI>
 928    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT
 929        : m_data(static_cast<local_limb_type>(i) & limb_mask),
 930          m_sign(false) {}
 931    template <class UI>
 932    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == checked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<UI>())))
 933        : m_data(static_cast<local_limb_type>(i) & limb_mask), m_sign(false) { check_in_range(i); }
 934    template <class F>
 935    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(F i, typename boost::enable_if_c<is_floating_point<F>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT
 936        : m_data(static_cast<local_limb_type>(std::fabs(i)) & limb_mask),
 937          m_sign(i < 0) {}
 938    template <class F>
 939    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(F i, typename boost::enable_if_c<is_floating_point<F>::value && (Checked == checked)>::type const* = 0)
 940        : m_data(static_cast<local_limb_type>(std::fabs(i)) & limb_mask), m_sign(i < 0) { check_in_range(i); }
 941 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
 942    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<>) BOOST_NOEXCEPT
 943        : m_data(static_cast<local_limb_type>(0u)),
 944          m_sign(false)
 945    {}
 946    template <limb_type a>
 947    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a>) BOOST_NOEXCEPT
 948        : m_data(static_cast<local_limb_type>(a)),
 949          m_sign(false) {}
 950    template <limb_type a, limb_type b>
 951    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a, b>) BOOST_NOEXCEPT
 952        : m_data(static_cast<local_limb_type>(a) | (static_cast<local_limb_type>(b) << bits_per_limb)),
 953          m_sign(false) {}
 954    BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& a, const literals::detail::negate_tag&) BOOST_NOEXCEPT
 955        : m_data(a.m_data),
 956          m_sign(a.m_data ? !a.m_sign : false) {}
 957 #endif
 958 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 959    //
 960    // These are deprecated in C++20 unless we make them explicit:
 961    //
 962    constexpr cpp_int_base& operator=(const cpp_int_base&) = default;
 963 #endif
 964    //
 965    // Helper functions for getting at our internal data, and manipulating storage:
 966    //
 967    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size() const BOOST_NOEXCEPT { return 1; }
 968    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() BOOST_NOEXCEPT { return &m_data; }
 969    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs() const BOOST_NOEXCEPT { return &m_data; }
 970    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR bool sign() const BOOST_NOEXCEPT { return m_sign; }
 971    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) BOOST_NOEXCEPT
 972    {
 973       m_sign = b;
 974       // Check for zero value:
 975       if (m_sign && !m_data)
 976       {
 977          m_sign = false;
 978       }
 979    }
 980    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(unsigned /* new_size */, unsigned min_size)
 981    {
 982       detail::verify_new_size(2, min_size, checked_type());
 983    }
 984    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
 985    {
 986       if (!m_data)
 987          m_sign = false; // zero is always unsigned
 988       detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
 989       m_data &= limb_mask;
 990    }
 991
 992    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT : m_data(0), m_sign(false) {}
 993    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
 994        : m_data(o.m_data),
 995          m_sign(o.m_sign) {}
 996    //~cpp_int_base() BOOST_NOEXCEPT {}
 997    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void assign(const cpp_int_base& o) BOOST_NOEXCEPT
 998    {
 999       m_data = o.m_data;
1000       m_sign = o.m_sign;
1001    }
1002    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void negate() BOOST_NOEXCEPT
1003    {
1004       m_sign = !m_sign;
1005       // Check for zero value:
1006       if (m_data == 0)
1007       {
1008          m_sign = false;
1009       }
1010    }
1011    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR bool isneg() const BOOST_NOEXCEPT
1012    {
1013       return m_sign;
1014    }
1015    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
1016    {
1017       std_constexpr::swap(m_sign, o.m_sign);
1018       std_constexpr::swap(m_data, o.m_data);
1019    }
1020 };
1021 //
1022 // Backend for unsigned fixed precision (i.e. no allocator) type which will fit entirely inside a "double_limb_type":
1023 //
1024 template <unsigned MinBits, cpp_int_check_type Checked>
1025 struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, true>
1026 {
1027    typedef typename trivial_limb_type<MinBits>::type local_limb_type;
1028    typedef local_limb_type*                          limb_pointer;
1029    typedef const local_limb_type*                    const_limb_pointer;
1030
1031  private:
1032    BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(local_limb_type) * CHAR_BIT);
1033    BOOST_STATIC_CONSTANT(local_limb_type, limb_mask = limb_bits != MinBits ? static_cast<local_limb_type>(static_cast<local_limb_type>(~local_limb_type(0)) >> (limb_bits - MinBits))
1034                                                                            : static_cast<local_limb_type>(~local_limb_type(0)));
1035
1036    local_limb_type m_data;
1037
1038    typedef mpl::int_<Checked> checked_type;
1039
1040    //
1041    // Interface invariants:
1042    //
1043    BOOST_STATIC_ASSERT_MSG(MinBits <= sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
1044
1045  protected:
1046    template <class T>
1047    BOOST_MP_CXX14_CONSTEXPR typename boost::disable_if_c<std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits)>::type
1048    check_in_range(T val, const mpl::int_<checked>&, const boost::false_type&)
1049    {
1050       typedef typename common_type<T, local_limb_type>::type common_type;
1051
1052       if (static_cast<common_type>(val) > limb_mask)
1053          BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
1054    }
1055    template <class T>
1056    BOOST_MP_CXX14_CONSTEXPR void check_in_range(T val, const mpl::int_<checked>&, const boost::true_type&)
1057    {
1058       typedef typename common_type<T, local_limb_type>::type common_type;
1059
1060       if (static_cast<common_type>(val) > limb_mask)
1061          BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
1062       if (val < 0)
1063          BOOST_THROW_EXCEPTION(std::range_error("The argument to an unsigned cpp_int constructor was negative."));
1064    }
1065    template <class T, int C, bool B>
1066    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void check_in_range(T, const mpl::int_<C>&, const boost::integral_constant<bool, B>&) BOOST_NOEXCEPT {}
1067
1068    template <class T>
1069    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void check_in_range(T val) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<T>(), checked_type(), is_signed<T>())))
1070    {
1071       check_in_range(val, checked_type(), is_signed<T>());
1072    }
1073
1074  public:
1075    //
1076    // Direct construction:
1077    //
1078 #ifdef __MSVC_RUNTIME_CHECKS
1079    template <class SI>
1080    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT
1081        : m_data(i < 0 ? (1 + ~static_cast<local_limb_type>(-i & limb_mask)) & limb_mask : static_cast<local_limb_type>(i & limb_mask))
1082    {}
1083    template <class SI>
1084    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == checked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
1085        : m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i & limb_mask) : static_cast<local_limb_type>(i & limb_mask)) { check_in_range(i); }
1086    template <class UI>
1087    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT
1088        : m_data(static_cast<local_limb_type>(i& limb_mask)) {}
1089    template <class UI>
1090    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == checked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<UI>())))
1091        : m_data(static_cast<local_limb_type>(i & limb_mask)) { check_in_range(i); }
1092 #else
1093    template <class SI>
1094    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT
1095        : m_data(i < 0 ? (1 + ~static_cast<local_limb_type>(-i)) & limb_mask : static_cast<local_limb_type>(i) & limb_mask)
1096    {}
1097    template <class SI>
1098    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(SI i, typename boost::enable_if_c<is_signed<SI>::value && (Checked == checked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<SI>())))
1099        : m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)) { check_in_range(i); }
1100    template <class UI>
1101    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT
1102        : m_data(static_cast<local_limb_type>(i) & limb_mask) {}
1103    template <class UI>
1104    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(UI i, typename boost::enable_if_c<is_unsigned<UI>::value && (Checked == checked)>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_base>().check_in_range(std::declval<UI>())))
1105        : m_data(static_cast<local_limb_type>(i)) { check_in_range(i); }
1106 #endif
1107    template <class F>
1108    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_base(F i, typename boost::enable_if<is_floating_point<F> >::type const* = 0) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
1109        : m_data(static_cast<local_limb_type>(std::fabs(i)) & limb_mask)
1110    {
1111       check_in_range(i);
1112       if (i < 0)
1113          negate();
1114    }
1115 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
1116    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<>) BOOST_NOEXCEPT
1117        : m_data(static_cast<local_limb_type>(0u))
1118    {}
1119    template <limb_type a>
1120    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a>) BOOST_NOEXCEPT
1121        : m_data(static_cast<local_limb_type>(a)) {}
1122    template <limb_type a, limb_type b>
1123    BOOST_CONSTEXPR cpp_int_base(literals::detail::value_pack<a, b>) BOOST_NOEXCEPT
1124        : m_data(static_cast<local_limb_type>(a) | (static_cast<local_limb_type>(b) << bits_per_limb)) {}
1125 #endif
1126 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
1127    //
1128    // These are deprecated in C++20 unless we make them explicit:
1129    //
1130    constexpr cpp_int_base& operator=(const cpp_int_base&) = default;
1131 #endif
1132    //
1133    // Helper functions for getting at our internal data, and manipulating storage:
1134    //
1135    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size() const BOOST_NOEXCEPT { return 1; }
1136    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR limb_pointer limbs() BOOST_NOEXCEPT { return &m_data; }
1137    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR const_limb_pointer limbs() const BOOST_NOEXCEPT { return &m_data; }
1138    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign() const BOOST_NOEXCEPT { return false; }
1139    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void sign(bool b) BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
1140    {
1141       if (b)
1142          negate();
1143    }
1144    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void resize(unsigned, unsigned min_size)
1145    {
1146       detail::verify_new_size(2, min_size, checked_type());
1147    }
1148    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void normalize() BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
1149    {
1150       detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
1151       m_data &= limb_mask;
1152    }
1153
1154    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT : m_data(0) {}
1155    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
1156        : m_data(o.m_data) {}
1157    //~cpp_int_base() BOOST_NOEXCEPT {}
1158    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void assign(const cpp_int_base& o) BOOST_NOEXCEPT
1159    {
1160       m_data = o.m_data;
1161    }
1162    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void negate() BOOST_MP_NOEXCEPT_IF((Checked == unchecked))
1163    {
1164       if (Checked == checked)
1165       {
1166          BOOST_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned type."));
1167       }
1168       m_data = ~m_data;
1169       ++m_data;
1170    }
1171    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool isneg() const BOOST_NOEXCEPT
1172    {
1173       return false;
1174    }
1175    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
1176    {
1177       std_constexpr::swap(m_data, o.m_data);
1178    }
1179 };
1180 //
1181 // Traits class, lets us know whether type T can be directly converted to the base type,
1182 // used to enable/disable constructors etc:
1183 //
1184 template <class Arg, class Base>
1185 struct is_allowed_cpp_int_base_conversion : public mpl::if_c<
1186                                                 is_same<Arg, limb_type>::value || is_same<Arg, signed_limb_type>::value
1187 #if BOOST_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
1188                                                     || is_same<Arg, double_limb_type>::value || is_same<Arg, signed_double_limb_type>::value
1189 #endif
1190 #if defined(BOOST_MP_USER_DEFINED_LITERALS)
1191                                                     || literals::detail::is_value_pack<Arg>::value
1192 #endif
1193                                                     || (is_trivial_cpp_int<Base>::value && is_arithmetic<Arg>::value),
1194                                                 mpl::true_,
1195                                                 mpl::false_>::type
1196 {};
1197 //
1198 // Now the actual backend, normalising parameters passed to the base class:
1199 //
1200 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
1201 struct cpp_int_backend
1202     : public cpp_int_base<
1203           min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1204           max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
1205           SignType,
1206           Checked,
1207           Allocator,
1208           is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>
1209 {
1210    typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> self_type;
1211    typedef cpp_int_base<
1212        min_precision<self_type>::value,
1213        max_precision<self_type>::value,
1214        SignType,
1215        Checked,
1216        Allocator,
1217        is_trivial_cpp_int<self_type>::value>
1218        base_type;
1219    typedef mpl::bool_<is_trivial_cpp_int<self_type>::value> trivial_tag;
1220
1221  public:
1222    typedef typename mpl::if_<
1223        trivial_tag,
1224        mpl::list<
1225            signed char, short, int, long,
1226            boost::long_long_type, signed_double_limb_type>,
1227        mpl::list<signed_limb_type, signed_double_limb_type> >::type signed_types;
1228    typedef typename mpl::if_<
1229        trivial_tag,
1230        mpl::list<unsigned char, unsigned short, unsigned,
1231                  unsigned long, boost::ulong_long_type, double_limb_type>,
1232        mpl::list<limb_type, double_limb_type> >::type unsigned_types;
1233    typedef typename mpl::if_<
1234        trivial_tag,
1235        mpl::list<float, double, long double>,
1236        mpl::list<long double> >::type float_types;
1237    typedef mpl::int_<Checked>         checked_type;
1238
1239    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend() BOOST_NOEXCEPT {}
1240    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(const cpp_int_backend& o) BOOST_MP_NOEXCEPT_IF(boost::is_void<Allocator>::value) : base_type(o) {}
1241 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1242    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(cpp_int_backend&& o) BOOST_NOEXCEPT
1243        : base_type(static_cast<base_type&&>(o))
1244    {}
1245 #endif
1246    //
1247    // Direct construction from arithmetic type:
1248    //
1249    template <class Arg>
1250    BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(Arg i, typename boost::enable_if_c<is_allowed_cpp_int_base_conversion<Arg, base_type>::value>::type const* = 0) BOOST_MP_NOEXCEPT_IF(noexcept(base_type(std::declval<Arg>())))
1251        : base_type(i) {}
1252
1253  private:
1254    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1255    BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::true_ const&, mpl::true_ const&)
1256    {
1257       // Assigning trivial type to trivial type:
1258       this->check_in_range(*other.limbs());
1259       *this->limbs() = static_cast<typename self_type::local_limb_type>(*other.limbs());
1260       this->sign(other.sign());
1261       this->normalize();
1262    }
1263    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1264    BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::true_ const&, mpl::false_ const&)
1265    {
1266       // non-trivial to trivial narrowing conversion:
1267       double_limb_type v = *other.limbs();
1268       if (other.size() > 1)
1269       {
1270          v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
1271          if ((Checked == checked) && (other.size() > 2))
1272          {
1273             BOOST_THROW_EXCEPTION(std::range_error("Assignment of a cpp_int that is out of range for the target type."));
1274          }
1275       }
1276       *this = v;
1277       this->sign(other.sign());
1278       this->normalize();
1279    }
1280    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1281    BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::false_ const&, mpl::true_ const&)
1282    {
1283       // trivial to non-trivial, treat the trivial argument as if it were an unsigned arithmetic type, then set the sign afterwards:
1284       *this = static_cast<
1285           typename boost::multiprecision::detail::canonical<
1286               typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type,
1287               cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::type>(*other.limbs());
1288       this->sign(other.sign());
1289    }
1290    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1291    BOOST_MP_CXX14_CONSTEXPR void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::false_ const&, mpl::false_ const&)
1292    {
1293       // regular non-trivial to non-trivial assign:
1294       this->resize(other.size(), other.size());
1295
1296       unsigned count = (std::min)(other.size(), this->size());
1297       for (unsigned i = 0; i < count; ++i)
1298          this->limbs()[i] = other.limbs()[i];
1299          //std::memcpy(this->limbs(), other.limbs(), (std::min)(other.size(), this->size()) * sizeof(this->limbs()[0]));
1300
1301       this->sign(other.sign());
1302       this->normalize();
1303    }
1304
1305  public:
1306    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1307    BOOST_MP_CXX14_CONSTEXPR cpp_int_backend(
1308        const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
1309        typename boost::enable_if_c<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = 0)
1310        : base_type()
1311    {
1312       do_assign(
1313           other,
1314           mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
1315           mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1316    }
1317    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1318    explicit BOOST_MP_CXX14_CONSTEXPR cpp_int_backend(
1319        const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
1320        typename boost::disable_if_c<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = 0)
1321        : base_type()
1322    {
1323       do_assign(
1324           other,
1325           mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
1326           mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1327    }
1328    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1329    BOOST_MP_CXX14_CONSTEXPR cpp_int_backend& operator=(
1330        const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other)
1331    {
1332       do_assign(
1333           other,
1334           mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
1335           mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
1336       return *this;
1337    }
1338 #ifdef BOOST_MP_USER_DEFINED_LITERALS
1339    BOOST_CONSTEXPR cpp_int_backend(const cpp_int_backend& a, const literals::detail::negate_tag& tag)
1340        : base_type(static_cast<const base_type&>(a), tag)
1341    {}
1342 #endif
1343
1344    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_backend& operator=(const cpp_int_backend& o) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_backend>().assign(std::declval<const cpp_int_backend&>())))
1345    {
1346       this->assign(o);
1347       return *this;
1348    }
1349 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1350    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR cpp_int_backend& operator=(cpp_int_backend&& o) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<base_type&>() = std::declval<base_type>()))
1351    {
1352       *static_cast<base_type*>(this) = static_cast<base_type&&>(o);
1353       return *this;
1354    }
1355 #endif
1356  private:
1357    template <class A>
1358    BOOST_MP_CXX14_CONSTEXPR typename boost::enable_if<is_unsigned<A> >::type do_assign_arithmetic(A val, const mpl::true_&)
1359        BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_backend>().check_in_range(std::declval<A>())))
1360    {
1361       this->check_in_range(val);
1362       *this->limbs() = static_cast<typename self_type::local_limb_type>(val);
1363       this->sign(false);
1364       this->normalize();
1365    }
1366    template <class A>
1367    BOOST_MP_CXX14_CONSTEXPR typename boost::disable_if_c<is_unsigned<A>::value || !is_integral<A>::value>::type do_assign_arithmetic(A val, const mpl::true_&)
1368        BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_backend>().check_in_range(std::declval<A>())) && noexcept(std::declval<cpp_int_backend>().sign(true)))
1369    {
1370       this->check_in_range(val);
1371       *this->limbs() = (val < 0) ? static_cast<typename self_type::local_limb_type>(boost::multiprecision::detail::unsigned_abs(val)) : static_cast<typename self_type::local_limb_type>(val);
1372       this->sign(val < 0);
1373       this->normalize();
1374    }
1375    template <class A>
1376    BOOST_MP_CXX14_CONSTEXPR typename boost::enable_if_c<!is_integral<A>::value>::type do_assign_arithmetic(A val, const mpl::true_&)
1377    {
1378       this->check_in_range(val);
1379       *this->limbs() = (val < 0) ? static_cast<typename self_type::local_limb_type>(boost::multiprecision::detail::abs(val)) : static_cast<typename self_type::local_limb_type>(val);
1380       this->sign(val < 0);
1381       this->normalize();
1382    }
1383    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_assign_arithmetic(limb_type i, const mpl::false_&) BOOST_NOEXCEPT
1384    {
1385       this->resize(1, 1);
1386       *this->limbs() = i;
1387       this->sign(false);
1388    }
1389    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void do_assign_arithmetic(signed_limb_type i, const mpl::false_&) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_backend>().sign(true)))
1390    {
1391       this->resize(1, 1);
1392       *this->limbs() = static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(i));
1393       this->sign(i < 0);
1394    }
1395    BOOST_MP_CXX14_CONSTEXPR void do_assign_arithmetic(double_limb_type i, const mpl::false_&) BOOST_NOEXCEPT
1396    {
1397       BOOST_STATIC_ASSERT(sizeof(i) == 2 * sizeof(limb_type));
1398       BOOST_STATIC_ASSERT(base_type::internal_limb_count >= 2);
1399       typename base_type::limb_pointer p = this->limbs();
1400 #ifdef __MSVC_RUNTIME_CHECKS
1401       *p = static_cast<limb_type>(i & ~static_cast<limb_type>(0));
1402 #else
1403       *p = static_cast<limb_type>(i);
1404 #endif
1405       p[1] = static_cast<limb_type>(i >> base_type::limb_bits);
1406       this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
1407       this->sign(false);
1408    }
1409    BOOST_MP_CXX14_CONSTEXPR void do_assign_arithmetic(signed_double_limb_type i, const mpl::false_&) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_backend>().sign(true)))
1410    {
1411       BOOST_STATIC_ASSERT(sizeof(i) == 2 * sizeof(limb_type));
1412       BOOST_STATIC_ASSERT(base_type::internal_limb_count >= 2);
1413       bool             s = false;
1414       if (i < 0)
1415          s = true;
1416       double_limb_type ui = static_cast<double_limb_type>(boost::multiprecision::detail::unsigned_abs(i));
1417       typename base_type::limb_pointer p = this->limbs();
1418 #ifdef __MSVC_RUNTIME_CHECKS
1419       *p = static_cast<limb_type>(ui & ~static_cast<limb_type>(0));
1420 #else
1421       *p = static_cast<limb_type>(ui);
1422 #endif
1423       p[1] = static_cast<limb_type>(ui >> base_type::limb_bits);
1424       this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
1425       this->sign(s);
1426    }
1427
1428    BOOST_MP_CXX14_CONSTEXPR void do_assign_arithmetic(long double a, const mpl::false_&)
1429    {
1430       using default_ops::eval_add;
1431       using default_ops::eval_subtract;
1432       using std::floor;
1433       using std::frexp;
1434       using std::ldexp;
1435
1436       if (a < 0)
1437       {
1438          do_assign_arithmetic(-a, mpl::false_());
1439          this->sign(true);
1440          return;
1441       }
1442
1443       if (a == 0)
1444       {
1445          *this = static_cast<limb_type>(0u);
1446       }
1447
1448       if (a == 1)
1449       {
1450          *this = static_cast<limb_type>(1u);
1451       }
1452
1453       if ((boost::math::isinf)(a) || (boost::math::isnan)(a))
1454       {
1455          BOOST_THROW_EXCEPTION(std::runtime_error("Cannot convert a non-finite number to an integer."));
1456       }
1457
1458       int         e = 0;
1459       long double f(0), term(0);
1460       *this = static_cast<limb_type>(0u);
1461
1462       f = frexp(a, &e);
1463
1464 #ifdef BOOST_NO_CXX11_CONSTEXPR
1465       static const limb_type shift = std::numeric_limits<limb_type>::digits;
1466 #else
1467       constexpr limb_type shift = std::numeric_limits<limb_type>::digits;
1468 #endif
1469
1470       while (f)
1471       {
1472          // extract int sized bits from f:
1473          f    = ldexp(f, shift);
1474          term = floor(f);
1475          e -= shift;
1476          eval_left_shift(*this, shift);
1477          if (term > 0)
1478             eval_add(*this, static_cast<limb_type>(term));
1479          else
1480             eval_subtract(*this, static_cast<limb_type>(-term));
1481          f -= term;
1482       }
1483       if (e > 0)
1484          eval_left_shift(*this, e);
1485       else if (e < 0)
1486          eval_right_shift(*this, -e);
1487    }
1488
1489  public:
1490    template <class Arithmetic>
1491    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename boost::enable_if_c<!boost::multiprecision::detail::is_byte_container<Arithmetic>::value, cpp_int_backend&>::type operator=(Arithmetic val) BOOST_MP_NOEXCEPT_IF(noexcept(std::declval<cpp_int_backend>().do_assign_arithmetic(std::declval<Arithmetic>(), trivial_tag())))
1492    {
1493       do_assign_arithmetic(val, trivial_tag());
1494       return *this;
1495    }
1496
1497  private:
1498    void do_assign_string(const char* s, const mpl::true_&)
1499    {
1500       std::size_t n  = s ? std::strlen(s) : 0;
1501       *this          = 0;
1502       unsigned radix = 10;
1503       bool     isneg = false;
1504       if (n && (*s == '-'))
1505       {
1506          --n;
1507          ++s;
1508          isneg = true;
1509       }
1510       if (n && (*s == '0'))
1511       {
1512          if ((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
1513          {
1514             radix = 16;
1515             s += 2;
1516             n -= 2;
1517          }
1518          else
1519          {
1520             radix = 8;
1521             n -= 1;
1522          }
1523       }
1524       if (n)
1525       {
1526          unsigned val;
1527          while (*s)
1528          {
1529             if (*s >= '0' && *s <= '9')
1530                val = *s - '0';
1531             else if (*s >= 'a' && *s <= 'f')
1532                val = 10 + *s - 'a';
1533             else if (*s >= 'A' && *s <= 'F')
1534                val = 10 + *s - 'A';
1535             else
1536                val = radix + 1;
1537             if (val >= radix)
1538             {
1539                BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1540             }
1541             *this->limbs() = detail::checked_multiply(*this->limbs(), static_cast<typename base_type::local_limb_type>(radix), checked_type());
1542             *this->limbs() = detail::checked_add(*this->limbs(), static_cast<typename base_type::local_limb_type>(val), checked_type());
1543             ++s;
1544          }
1545       }
1546       if (isneg)
1547          this->negate();
1548    }
1549    void do_assign_string(const char* s, const mpl::false_&)
1550    {
1551       using default_ops::eval_add;
1552       using default_ops::eval_multiply;
1553       std::size_t n  = s ? std::strlen(s) : 0;
1554       *this          = static_cast<limb_type>(0u);
1555       unsigned radix = 10;
1556       bool     isneg = false;
1557       if (n && (*s == '-'))
1558       {
1559          --n;
1560          ++s;
1561          isneg = true;
1562       }
1563       if (n && (*s == '0'))
1564       {
1565          if ((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
1566          {
1567             radix = 16;
1568             s += 2;
1569             n -= 2;
1570          }
1571          else
1572          {
1573             radix = 8;
1574             n -= 1;
1575          }
1576       }
1577       //
1578       // Exception guarantee: create the result in stack variable "result"
1579       // then do a swap at the end.  In the event of a throw, *this will
1580       // be left unchanged.
1581       //
1582       cpp_int_backend result;
1583       if (n)
1584       {
1585          if (radix == 16)
1586          {
1587             while (*s == '0')
1588                ++s;
1589             std::size_t bitcount = 4 * std::strlen(s);
1590             limb_type   val;
1591             std::size_t limb, shift;
1592             if (bitcount > 4)
1593                bitcount -= 4;
1594             else
1595                bitcount = 0;
1596             std::size_t newsize = bitcount / (sizeof(limb_type) * CHAR_BIT) + 1;
1597             result.resize(static_cast<unsigned>(newsize), static_cast<unsigned>(newsize)); // will throw if this is a checked integer that cannot be resized
1598             std::memset(result.limbs(), 0, result.size() * sizeof(limb_type));
1599             while (*s)
1600             {
1601                if (*s >= '0' && *s <= '9')
1602                   val = *s - '0';
1603                else if (*s >= 'a' && *s <= 'f')
1604                   val = 10 + *s - 'a';
1605                else if (*s >= 'A' && *s <= 'F')
1606                   val = 10 + *s - 'A';
1607                else
1608                {
1609                   BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1610                }
1611                limb  = bitcount / (sizeof(limb_type) * CHAR_BIT);
1612                shift = bitcount % (sizeof(limb_type) * CHAR_BIT);
1613                val <<= shift;
1614                if (result.size() > limb)
1615                {
1616                   result.limbs()[limb] |= val;
1617                }
1618                ++s;
1619                bitcount -= 4;
1620             }
1621             result.normalize();
1622          }
1623          else if (radix == 8)
1624          {
1625             while (*s == '0')
1626                ++s;
1627             std::size_t bitcount = 3 * std::strlen(s);
1628             limb_type   val;
1629             std::size_t limb, shift;
1630             if (bitcount > 3)
1631                bitcount -= 3;
1632             else
1633                bitcount = 0;
1634             std::size_t newsize = bitcount / (sizeof(limb_type) * CHAR_BIT) + 1;
1635             result.resize(static_cast<unsigned>(newsize), static_cast<unsigned>(newsize)); // will throw if this is a checked integer that cannot be resized
1636             std::memset(result.limbs(), 0, result.size() * sizeof(limb_type));
1637             while (*s)
1638             {
1639                if (*s >= '0' && *s <= '7')
1640                   val = *s - '0';
1641                else
1642                {
1643                   BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
1644                }
1645                limb  = bitcount / (sizeof(limb_type) * CHAR_BIT);
1646                shift = bitcount % (sizeof(limb_type) * CHAR_BIT);
1647                if (result.size() > limb)
1648                {
1649                   result.limbs()[limb] |= (val << shift);
1650                   if (shift > sizeof(limb_type) * CHAR_BIT - 3)
1651                   {
1652                      // Deal with the bits in val that overflow into the next limb:
1653                      val >>= (sizeof(limb_type) * CHAR_BIT - shift);
1654                      if (val)
1655                      {
1656                         // If this is the most-significant-limb, we may need to allocate an extra one for the overflow:
1657                         if (limb + 1 == newsize)
1658                            result.resize(static_cast<unsigned>(newsize + 1), static_cast<unsigned>(newsize + 1));
1659                         if (result.size() > limb + 1)
1660                         {
1661                            result.limbs()[limb + 1] |= val;
1662                         }
1663                      }
1664                   }
1665                }
1666                ++s;
1667                bitcount -= 3;
1668             }
1669             result.normalize();
1670          }
1671          else
1672          {
1673             // Base 10, we extract blocks of size 10^9 at a time, that way
1674             // the number of multiplications is kept to a minimum:
1675             limb_type block_mult = max_block_10;
1676             while (*s)
1677             {
1678                limb_type block = 0;
1679                for (unsigned i = 0; i < digits_per_block_10; ++i)
1680                {
1681                   limb_type val;
1682                   if (*s >= '0' && *s <= '9')
1683                      val = *s - '0';
1684                   else
1685                      BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected character encountered in input."));
1686                   block *= 10;
1687                   block += val;
1688                   if (!*++s)
1689                   {
1690                      block_mult = block_multiplier(i);
1691                      break;
1692                   }
1693                }
1694                eval_multiply(result, block_mult);
1695                eval_add(result, block);
1696             }
1697          }
1698       }
1699       if (isneg)
1700          result.negate();
1701       result.swap(*this);
1702    }
1703
1704  public:
1705    cpp_int_backend& operator=(const char* s)
1706    {
1707       do_assign_string(s, trivial_tag());
1708       return *this;
1709    }
1710    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR void swap(cpp_int_backend& o) BOOST_NOEXCEPT
1711    {
1712       this->do_swap(o);
1713    }
1714
1715  private:
1716    std::string do_get_trivial_string(std::ios_base::fmtflags f, const mpl::false_&) const
1717    {
1718       typedef typename mpl::if_c<sizeof(typename base_type::local_limb_type) == 1, unsigned, typename base_type::local_limb_type>::type io_type;
1719       if (this->sign() && (((f & std::ios_base::hex) == std::ios_base::hex) || ((f & std::ios_base::oct) == std::ios_base::oct)))
1720          BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1721       std::stringstream ss;
1722       ss.flags(f & ~std::ios_base::showpos);
1723       ss << static_cast<io_type>(*this->limbs());
1724       std::string result;
1725       if (this->sign())
1726          result += '-';
1727       else if (f & std::ios_base::showpos)
1728          result += '+';
1729       result += ss.str();
1730       return result;
1731    }
1732    std::string do_get_trivial_string(std::ios_base::fmtflags f, const mpl::true_&) const
1733    {
1734       // Even though we have only one limb, we can't do IO on it :-(
1735       int base = 10;
1736       if ((f & std::ios_base::oct) == std::ios_base::oct)
1737          base = 8;
1738       else if ((f & std::ios_base::hex) == std::ios_base::hex)
1739          base = 16;
1740       std::string result;
1741
1742       unsigned Bits = sizeof(typename base_type::local_limb_type) * CHAR_BIT;
1743
1744       if (base == 8 || base == 16)
1745       {
1746          if (this->sign())
1747             BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1748          limb_type                           shift = base == 8 ? 3 : 4;
1749          limb_type                           mask  = static_cast<limb_type>((1u << shift) - 1);
1750          typename base_type::local_limb_type v     = *this->limbs();
1751          result.assign(Bits / shift + (Bits % shift ? 1 : 0), '0');
1752          std::string::difference_type pos      = result.size() - 1;
1753          char                         letter_a = f & std::ios_base::uppercase ? 'A' : 'a';
1754          for (unsigned i = 0; i < Bits / shift; ++i)
1755          {
1756             char c = '0' + static_cast<char>(v & mask);
1757             if (c > '9')
1758                c += letter_a - '9' - 1;
1759             result[pos--] = c;
1760             v >>= shift;
1761          }
1762          if (Bits % shift)
1763          {
1764             mask   = static_cast<limb_type>((1u << (Bits % shift)) - 1);
1765             char c = '0' + static_cast<char>(v & mask);
1766             if (c > '9')
1767                c += letter_a - '9';
1768             result[pos] = c;
1769          }
1770          //
1771          // Get rid of leading zeros:
1772          //
1773          std::string::size_type n = result.find_first_not_of('0');
1774          if (!result.empty() && (n == std::string::npos))
1775             n = result.size() - 1;
1776          result.erase(0, n);
1777          if (f & std::ios_base::showbase)
1778          {
1779             const char* pp = base == 8 ? "0" : (f & std::ios_base::uppercase) ? "0X" : "0x";
1780             result.insert(static_cast<std::string::size_type>(0), pp);
1781          }
1782       }
1783       else
1784       {
1785          result.assign(Bits / 3 + 1, '0');
1786          std::string::difference_type        pos = result.size() - 1;
1787          typename base_type::local_limb_type v(*this->limbs());
1788          bool                                neg = false;
1789          if (this->sign())
1790          {
1791             neg = true;
1792          }
1793          while (v)
1794          {
1795             result[pos] = (v % 10) + '0';
1796             --pos;
1797             v /= 10;
1798          }
1799          std::string::size_type n = result.find_first_not_of('0');
1800          result.erase(0, n);
1801          if (result.empty())
1802             result = "0";
1803          if (neg)
1804             result.insert(static_cast<std::string::size_type>(0), 1, '-');
1805          else if (f & std::ios_base::showpos)
1806             result.insert(static_cast<std::string::size_type>(0), 1, '+');
1807       }
1808       return result;
1809    }
1810    std::string do_get_string(std::ios_base::fmtflags f, const mpl::true_&) const
1811    {
1812 #ifdef BOOST_MP_NO_DOUBLE_LIMB_TYPE_IO
1813       return do_get_trivial_string(f, mpl::bool_<is_same<typename base_type::local_limb_type, double_limb_type>::value>());
1814 #else
1815       return do_get_trivial_string(f, mpl::bool_<false>());
1816 #endif
1817    }
1818    std::string do_get_string(std::ios_base::fmtflags f, const mpl::false_&) const
1819    {
1820       using default_ops::eval_get_sign;
1821       int base = 10;
1822       if ((f & std::ios_base::oct) == std::ios_base::oct)
1823          base = 8;
1824       else if ((f & std::ios_base::hex) == std::ios_base::hex)
1825          base = 16;
1826       std::string result;
1827
1828       unsigned Bits = this->size() * base_type::limb_bits;
1829
1830       if (base == 8 || base == 16)
1831       {
1832          if (this->sign())
1833             BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
1834          limb_type       shift = base == 8 ? 3 : 4;
1835          limb_type       mask  = static_cast<limb_type>((1u << shift) - 1);
1836          cpp_int_backend t(*this);
1837          result.assign(Bits / shift + ((Bits % shift) ? 1 : 0), '0');
1838          std::string::difference_type pos      = result.size() - 1;
1839          char                         letter_a = f & std::ios_base::uppercase ? 'A' : 'a';
1840          for (unsigned i = 0; i < Bits / shift; ++i)
1841          {
1842             char c = '0' + static_cast<char>(t.limbs()[0] & mask);
1843             if (c > '9')
1844                c += letter_a - '9' - 1;
1845             result[pos--] = c;
1846             eval_right_shift(t, shift);
1847          }
1848          if (Bits % shift)
1849          {
1850             mask   = static_cast<limb_type>((1u << (Bits % shift)) - 1);
1851             char c = '0' + static_cast<char>(t.limbs()[0] & mask);
1852             if (c > '9')
1853                c += letter_a - '9';
1854             result[pos] = c;
1855          }
1856          //
1857          // Get rid of leading zeros:
1858          //
1859          std::string::size_type n = result.find_first_not_of('0');
1860          if (!result.empty() && (n == std::string::npos))
1861             n = result.size() - 1;
1862          result.erase(0, n);
1863          if (f & std::ios_base::showbase)
1864          {
1865             const char* pp = base == 8 ? "0" : (f & std::ios_base::uppercase) ? "0X" : "0x";
1866             result.insert(static_cast<std::string::size_type>(0), pp);
1867          }
1868       }
1869       else
1870       {
1871          result.assign(Bits / 3 + 1, '0');
1872          std::string::difference_type pos = result.size() - 1;
1873          cpp_int_backend              t(*this);
1874          cpp_int_backend              r;
1875          bool                         neg = false;
1876          if (t.sign())
1877          {
1878             t.negate();
1879             neg = true;
1880          }
1881          if (this->size() == 1)
1882          {
1883             result = boost::lexical_cast<std::string>(t.limbs()[0]);
1884          }
1885          else
1886          {
1887             cpp_int_backend block10;
1888             block10 = max_block_10;
1889             while (eval_get_sign(t) != 0)
1890             {
1891                cpp_int_backend t2;
1892                divide_unsigned_helper(&t2, t, block10, r);
1893                t           = t2;
1894                limb_type v = r.limbs()[0];
1895                for (unsigned i = 0; i < digits_per_block_10; ++i)
1896                {
1897                   char c = '0' + v % 10;
1898                   v /= 10;
1899                   result[pos] = c;
1900                   if (pos-- == 0)
1901                      break;
1902                }
1903             }
1904          }
1905          std::string::size_type n = result.find_first_not_of('0');
1906          result.erase(0, n);
1907          if (result.empty())
1908             result = "0";
1909          if (neg)
1910             result.insert(static_cast<std::string::size_type>(0), 1, '-');
1911          else if (f & std::ios_base::showpos)
1912             result.insert(static_cast<std::string::size_type>(0), 1, '+');
1913       }
1914       return result;
1915    }
1916
1917  public:
1918    std::string str(std::streamsize /*digits*/, std::ios_base::fmtflags f) const
1919    {
1920       return do_get_string(f, trivial_tag());
1921    }
1922
1923  private:
1924    template <class Container>
1925    void construct_from_container(const Container& c, const mpl::false_&)
1926    {
1927       //
1928       // We assume that c is a sequence of (unsigned) bytes with the most significant byte first:
1929       //
1930       unsigned newsize = static_cast<unsigned>(c.size() / sizeof(limb_type));
1931       if (c.size() % sizeof(limb_type))
1932       {
1933          ++newsize;
1934       }
1935       if (newsize)
1936       {
1937          this->resize(newsize, newsize); // May throw
1938          std::memset(this->limbs(), 0, this->size());
1939          typename Container::const_iterator i(c.begin()), j(c.end());
1940          unsigned                           byte_location = static_cast<unsigned>(c.size() - 1);
1941          while (i != j)
1942          {
1943             unsigned limb  = byte_location / sizeof(limb_type);
1944             unsigned shift = (byte_location % sizeof(limb_type)) * CHAR_BIT;
1945             if (this->size() > limb)
1946                this->limbs()[limb] |= static_cast<limb_type>(static_cast<unsigned char>(*i)) << shift;
1947             ++i;
1948             --byte_location;
1949          }
1950       }
1951    }
1952    template <class Container>
1953    BOOST_MP_CXX14_CONSTEXPR void construct_from_container(const Container& c, const mpl::true_&)
1954    {
1955       //
1956       // We assume that c is a sequence of (unsigned) bytes with the most significant byte first:
1957       //
1958       typedef typename base_type::local_limb_type local_limb_type;
1959       *this->limbs() = 0;
1960       if (c.size())
1961       {
1962          typename Container::const_iterator i(c.begin()), j(c.end());
1963          unsigned                           byte_location = static_cast<unsigned>(c.size() - 1);
1964          while (i != j)
1965          {
1966             unsigned limb  = byte_location / sizeof(local_limb_type);
1967             unsigned shift = (byte_location % sizeof(local_limb_type)) * CHAR_BIT;
1968             if (limb == 0)
1969                this->limbs()[0] |= static_cast<limb_type>(static_cast<unsigned char>(*i)) << shift;
1970             ++i;
1971             --byte_location;
1972          }
1973       }
1974    }
1975
1976  public:
1977    template <class Container>
1978    BOOST_MP_CXX14_CONSTEXPR cpp_int_backend(const Container& c, typename boost::enable_if_c<boost::multiprecision::detail::is_byte_container<Container>::value>::type const* = 0)
1979    {
1980       //
1981       // We assume that c is a sequence of (unsigned) bytes with the most significant byte first:
1982       //
1983       construct_from_container(c, trivial_tag());
1984    }
1985    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1986    BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::false_&, const mpl::false_&) const BOOST_NOEXCEPT
1987    {
1988       if (this->sign() != o.sign())
1989          return this->sign() ? -1 : 1;
1990
1991       // Only do the compare if the same sign:
1992       int result = compare_unsigned(o);
1993
1994       if (this->sign())
1995          result = -result;
1996       return result;
1997    }
1998    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
1999    BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::true_&, const mpl::false_&) const
2000    {
2001       cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t(*this);
2002       return t.compare(o);
2003    }
2004    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2005    BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::false_&, const mpl::true_&) const
2006    {
2007       cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> t(o);
2008       return compare(t);
2009    }
2010    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2011    BOOST_MP_CXX14_CONSTEXPR int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::true_&, const mpl::true_&) const BOOST_NOEXCEPT
2012    {
2013       if (this->sign())
2014       {
2015          if (o.sign())
2016          {
2017             return *this->limbs() < *o.limbs() ? 1 : (*this->limbs() > *o.limbs() ? -1 : 0);
2018          }
2019          else
2020             return -1;
2021       }
2022       else
2023       {
2024          if (o.sign())
2025             return 1;
2026          return *this->limbs() < *o.limbs() ? -1 : (*this->limbs() > *o.limbs() ? 1 : 0);
2027       }
2028    }
2029    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2030    BOOST_MP_CXX14_CONSTEXPR int compare(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) const BOOST_NOEXCEPT
2031    {
2032       typedef mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>      t1;
2033       typedef mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value> t2;
2034       return compare_imp(o, t1(), t2());
2035    }
2036    template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2037    BOOST_MP_CXX14_CONSTEXPR int compare_unsigned(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o) const BOOST_NOEXCEPT
2038    {
2039       if (this->size() != o.size())
2040       {
2041          return this->size() > o.size() ? 1 : -1;
2042       }
2043       typename base_type::const_limb_pointer pa = this->limbs();
2044       typename base_type::const_limb_pointer pb = o.limbs();
2045       for (int i = this->size() - 1; i >= 0; --i)
2046       {
2047          if (pa[i] != pb[i])
2048             return pa[i] > pb[i] ? 1 : -1;
2049       }
2050       return 0;
2051    }
2052    template <class Arithmetic>
2053    BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename boost::enable_if<is_arithmetic<Arithmetic>, int>::type compare(Arithmetic i) const
2054    {
2055       // braindead version:
2056       cpp_int_backend t;
2057       t = i;
2058       return compare(t);
2059    }
2060 };
2061
2062 } // namespace backends
2063
2064 namespace default_ops {
2065
2066 template <class Backend>
2067 struct double_precision_type;
2068
2069 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
2070 struct double_precision_type<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
2071 {
2072    typedef typename mpl::if_c<
2073        backends::is_fixed_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
2074        backends::cpp_int_backend<
2075            (is_void<Allocator>::value ? 2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value
2076                                       : MinBits),
2077            2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
2078            SignType,
2079            Checked,
2080            Allocator>,
2081        backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::type type;
2082 };
2083
2084 } // namespace default_ops
2085
2086 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked>
2087 struct expression_template_default<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, void> >
2088 {
2089    static const expression_template_option value = et_off;
2090 };
2091
2092 using boost::multiprecision::backends::cpp_int_backend;
2093
2094 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
2095 struct number_category<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> > : public mpl::int_<number_kind_integer>
2096 {};
2097
2098 typedef number<cpp_int_backend<> >           cpp_int;
2099 typedef rational_adaptor<cpp_int_backend<> > cpp_rational_backend;
2100 typedef number<cpp_rational_backend>         cpp_rational;
2101
2102 // Fixed precision unsigned types:
2103 typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> >   uint128_t;
2104 typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> >   uint256_t;
2105 typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> >   uint512_t;
2106 typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t;
2107
2108 // Fixed precision signed types:
2109 typedef number<cpp_int_backend<128, 128, signed_magnitude, unchecked, void> >   int128_t;
2110 typedef number<cpp_int_backend<256, 256, signed_magnitude, unchecked, void> >   int256_t;
2111 typedef number<cpp_int_backend<512, 512, signed_magnitude, unchecked, void> >   int512_t;
2112 typedef number<cpp_int_backend<1024, 1024, signed_magnitude, unchecked, void> > int1024_t;
2113
2114 // Over again, but with checking enabled this time:
2115 typedef number<cpp_int_backend<0, 0, signed_magnitude, checked> >           checked_cpp_int;
2116 typedef rational_adaptor<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_rational_backend;
2117 typedef number<checked_cpp_rational_backend>                                checked_cpp_rational;
2118 // Fixed precision unsigned types:
2119 typedef number<cpp_int_backend<128, 128, unsigned_magnitude, checked, void> >   checked_uint128_t;
2120 typedef number<cpp_int_backend<256, 256, unsigned_magnitude, checked, void> >   checked_uint256_t;
2121 typedef number<cpp_int_backend<512, 512, unsigned_magnitude, checked, void> >   checked_uint512_t;
2122 typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, checked, void> > checked_uint1024_t;
2123
2124 // Fixed precision signed types:
2125 typedef number<cpp_int_backend<128, 128, signed_magnitude, checked, void> >   checked_int128_t;
2126 typedef number<cpp_int_backend<256, 256, signed_magnitude, checked, void> >   checked_int256_t;
2127 typedef number<cpp_int_backend<512, 512, signed_magnitude, checked, void> >   checked_int512_t;
2128 typedef number<cpp_int_backend<1024, 1024, signed_magnitude, checked, void> > checked_int1024_t;
2129
2130 #ifdef BOOST_NO_SFINAE_EXPR
2131
2132 namespace detail {
2133
2134 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
2135 struct is_explicitly_convertible<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> > : public mpl::true_
2136 {};
2137
2138 } // namespace detail
2139 #endif
2140
2141 #ifdef _MSC_VER
2142 #pragma warning(pop)
2143 #endif
2144
2145 }} // namespace boost::multiprecision
2146
2147 //
2148 // Last of all we include the implementations of all the eval_* non member functions:
2149 //
2150 #include <boost/multiprecision/cpp_int/comparison.hpp>
2151 #include <boost/multiprecision/cpp_int/add.hpp>
2152 #include <boost/multiprecision/cpp_int/multiply.hpp>
2153 #include <boost/multiprecision/cpp_int/divide.hpp>
2154 #include <boost/multiprecision/cpp_int/bitwise.hpp>
2155 #include <boost/multiprecision/cpp_int/misc.hpp>
2156 #include <boost/multiprecision/cpp_int/limits.hpp>
2157 #ifdef BOOST_MP_USER_DEFINED_LITERALS
2158 #include <boost/multiprecision/cpp_int/literals.hpp>
2159 #endif
2160 #include <boost/multiprecision/cpp_int/serialize.hpp>
2161 #include <boost/multiprecision/cpp_int/import_export.hpp>
2162
2163 #endif