Proposal for Unbounded-Precision Integer Types

What’s New in this Revision

• removed the number-theoretic functions from unsigned_integer and integer;
• removed the support for random numbers from unsigned_integer;
• added integer_data_proxy for manipulating the internal representation of an integer object to provide advanced users with hooks for extended operations;
• renamed unsigned_integer to bits and gave it the same interface as std::bitset.

Overview

Programmers sometimes need to manipulate integer values that are too large to repesent with C++’s standard integer types. Doing a Google search for terms that describe large integers produces many hits for libraries that handle large integers. These libraries vary in quality, from hacks by beginners to sophisticated, professional implementations. Also, Java has unbounded precision integers as part of its standard class library.

One important use for unbounded-precision integers is cryptography. Cryptographic applications typically manipulate integer values of several hundred digits. If the C++ standard library provides facilities for such values it will make cryptographic applications easier to write and to port.

There have been two Committee papers proposing unbounded-precision integer libraries for C++: N1718 (2004) and N2143 (2007), both by M.J. Kronenburg. Nothing was done with these papers, in part because there was too much else going on in the Library Working Group at the time. Now that the Committee is looking to greatly expand the scope of the standard library, it’s time to reconsider unbounded-precision integers.

Design considerations

An unbounded-precision integer type is an integer type that does not impose pre-defined limits on the precision of the values that it can represent. Of course, in practice, unbounded precision can’t be achieved; sooner or later the system runs out of resources. So unbounded in this context means bounded only by the availability of system resources; there is no hard-coded limit to the number of digits in the value that an unbounded-precision integer type an represent.

Unbounded-precision integer types should interoperate with C++’s built-in integer types. Applying arithmetic operations to a mix of standard integer types and unbounded-precision integer types should just work. And to the extent possible, operations that can be applied to standard integer types should also be applicable, using the same syntax, to unbounded-precision integer types.

Unbounded-precision integer types should also provide operations that facilitate their use in areas that demand such types. Since there is a potentially unbounded list of operations that could be useful in applications that need unbounded-precision integer types, it is not practical to provide every useful operation. This proposal presents a small set of required operations and provides a facility for users to write their own extensions.

Design overview

This paper proposes two unbounded-precision integer types. The type integer represents signed integer values. The type bits represents an unbounded set of bit values.

To support interoperability, objects of either type can be constructed from values of any of the standard integer types. So code like this just works:

    integer i = 30000;
    integer j = 1000 * i;

    bits b = 0xFF;
    bits c = b & 0xAA;

Converting a negative number to an object of type bits sets the number to the complement of this initializer, so this code just works:

    bits b = -3; // sets b to ...11111100

This is easily implemented by storing a finite set of 1 bits (in this case, 0x03) and using a flag to indicate whether the actual value is represented by that set of bits or by its complement.

As currently specified, neither integer nor bits provides overloaded operators that take standard integer types. When an operation is applied to a standard integer type and an integer object or a bits object, the standard integer operand is converted to the appropriate unbounded-precision integer type and the operation is applied to the result. It is assumed that implementations will make this kind of mixed operation efficient by implementing a small-integer optimization, storing small values directly in the integer or bits object, and using heap storage when needed for larger values. This greatly simplifies the interface specification.

Objects of these types can be constructed from string representations (with the usual range of possible bases) and from an initializer list that holds unsigned 32-bit values.

Objects of type integer can also be constructed from values of floating-point types.

Values of type integer and of type bits can be freely inter-converted.

Bit manipulations on bits objects treat the value as having an unbounded number of bits above the highest bit stored in the object. As a result, the usual bit operations, &, |, and ^, can be applied to values of different sizes. Further, std::seminumeric::bits can be used as a replacement for std::bitset when limiting the object to a fixed number of bits is undesirable.

Issues

1. Allocators -- unbounded-precision integer types need to manage memory on the free store to hold their data. This suggests that users should be able to specify an allocator. But templatizing these types on an allocator would require that all of the arithmetic operations provide overloads for all of the standard integer types, because function template instantiation requires exact type matches, without conversions.
2. [resolved in N3542] Policy for out-of-bounds subtraction -- subtracting an bits value from a smaller value doesn’t have any specified semantics in this paper. This should probably throw an exception. Resolution: removed arithmetic operations on bits objects.
3. [resolved in N3542] Policy for out-of-bounds constructor arguments -- constructing an bits object from a negative value doesn’t have any specified semantics in this paper. This should probably throw an exception. Resolution: negative values produce complemented bit sets.
4. Policy for lossy conversions -- converting an bits or integer object to an integral type that cannot represent its value doesn’t have any specified semantics in this paper. Should this throw an exception?
5. [new in N3417] Rvalue overloads for arithmetic operations (Joe Gottman) -- many of the operations on the unbounded-precision types can be made more efficient by providing overloaded versions that take rvalue references. For example:

   integer operator+(integer&& lhs, const integer& rhs) {
       return std::move(lsh += rhs);
   }

6. [new in N3417] Functions for controlling when and how allocations occur (Joe Gottman) -- just as with std::string, many operations can be made faster by pre-allocating enough memory to hold the expected result. In some cases the desired capacity is best expressed in bits and in some cases in decimal digits, so the suggestion is to offer both:

   size_t capacity_in_bits() const;   // The number of bits the object can hold without reallocation.
   size_t capacity_in_digits() const; // The largest number n such that the object can hold n decimal
                                      // digits without reallocation.
   void reserve_bits(size_t n);       // Postcondition: capacity_in_bits() >= n.
   void reserve_digits(size_t n);     // Postcondition: capacity_in_digits() >= n.
   void shrink_to_fit()();            // A non-binding request to reduce memory usage.

7. [new in N3417] Support user-defined literals (Alisdair Meredith, Marc Glisse) -- obviously useful, but users might expect them to be constexpr, which they cannot, in general, be, because they need to allocate memory.
8. [new in N3417] Add noexcept specifications as appropriate (Alisdair Meredith) -- there are several that are obvious. In addition, if we require the small-object optimization, some or all of the constructors that take integral types can be noexcept.
9. [new in N3417] Add constexpr specifications as appropriate (Alisdair Meredith) -- although most functions can allocate memory, there are a few that could be marked constexpr. It’s not clear how useful this would be.
10. [new in N3417] Why do the bitshift operators take an int argument? (Alisdiar Meredith, Marc Glisse) -- this may be limiting, for example, on a 64-bit OS with a 32-bit int type. size_t or ptrdiff_t may be a better choice.
11. [resolved in N3542] [new in N3417] Why just one string type for string conversions? (Alisdair Meredith) -- there are four standard basic_string typedefs. Resolution: string operations are now fully templated.
12. [new in N3417] Converting to a string could use a mechanism for providing an allocator (Alisdair Meredith) -- for example,

    template<class charT, class Traits, class Alloc>
    void bits::load(basic_string<charT, Traits, Alloc>&);

13. [resolved in N3542] [new in N3417] Consider extending interface to more fully support dynamic bitsets (Alisdair Meredith) -- or maybe that should be a separate class, with shared implementation. Resolution: changed unsigned_integer to bits with same interface as std::bitset.
14. [resolved in N3542] [resolved in N3542] [new in N3417] powmod should be specified to run in constant time with identical cache access patterns for arguments of the same size (Jack Lloyd) -- this is important for cryptographic purposes, to avoid side-channel attacks. Resolution: removed powmod and provided a do-it-yourself solution.
15. [new in N3417] Need functions to interconvert with byte arrays (Jack Lloyd) -- quite a common need in cryptographic operations.
16. [resolved in N3542] [new in N3417] Add a typedef that gives the underlying representation type and an accessor that provides a pointer to the internal representation. (Jack Lloyd) -- some common cryptographic algorithms can’t be implemented with the interface in the proposal; adding these accessors makes it possible to implement them. Resolution: added class integer_data_proxy.
17. [resolved in N3542] [resolved in N3542] [new in N3417] Is the unsigned_integer type necessary? (Marc Glisse) -- if this is there to support bit manipulation, why not just specify those operations as undefined for negative numbers. Resolution: removed unsigned_integer and added bits, whose sole purpose is bit manipulation.
18. [new in N3417] Rounding of divisions and right shifts needs to be specified. (Marc Glisse) -- even if it’s obvious. Also, does mod return negative values?
19. [resolved in N3542] [new in N3417] The constructor that takes a string should be explicit. (Marc Glisse) Resolution: done.
20. [resolved in N3542] [new in N3417] Consider making to_string() a non-member function. (Daniel Krügler) -- this would be a good match with the existing to_string functions. Resolution: done for integer; bits has it as a member to match std::bitset.
21. [resolved in N3542] [new in N3417] Consider removing explicit operator std::string() const. (Daniel Krügler, Jens Maurer) -- to_string() is sufficient. Resolution: done.

Header <seminumeric> synopsis

namespace std {
namespace seminumeric {

/* class integer */

    class integer;
    class integer_data_proxy;

    void swap(integer& lhs, integer& rhs);

    // comparisons
    bool operator==(const integer& lhs, const integer& rhs);
    bool operator!=(const integer& lhs, const integer& rhs);
    bool operator<(const integer& lhs, const integer& rhs);
    bool operator<=(const integer& lhs, const integer& rhs);
    bool operator>(const integer& lhs, const integer& rhs);
    bool operator>=(const integer& lhs, const integer& rhs);

    // arithmetic operations
    integer operator+(const integer& lhs, const integer& rhs);
    integer operator-(const integer& lhs, const integer& rhs);
    integer operator*(const integer& lhs, const integer& rhs);
    integer operator/(const integer& lhs, const integer& rhs);
    integer operator%(const integer& lhs, const integer& rhs);

    std::pair<integer, integer> div(const integer& lhs, const integer& rhs);

    integer abs(const integer& val);

    integer operator<<(const integer& lhs, int shift);
    integer operator>>(const integer& lhs, int shift);

    // numeric operations
    integer sqr(const integer& val);
    integer sqrt(const integer& val);
    integer pow(const integer& val, const integer& exp);

    // conversions
    std::string to_string(const integer& val, int radix = 16);

    // I/O operations
    template <class CharT, class Traits>
        std::basic_ostream<CharT, Traits>& operator<<(
            std::basic_ostream<CharT, Traits>& str, const integer& val);
    template <class CharT, class Traits>
        std::basic_istream<CharT, Traits>& operator>>(
            std::basic_istream<CharT, Traits>& str, integer& val);

/* class bits */

    class bits;

    void swap(bits& lhs, bits& rhs);

    // logical operations
    bits operator&(const bits& lhs, const bits& rhs);
    bits operator|(const bits& lhs, const bits& rhs);
    bits operator^(const bits& lhs, const bits& rhs);

    // I/O operations
    template <class CharT, class Traits>
        std::basic_ostream<CharT, Traits>& operator<<(
            std::basic_ostream<CharT, Traits>& str, const bits& val);
    template <class CharT, class Traits>
        std::basic_istream<CharT, Traits>& operator>>(
            std::basic_istream<CharT, Traits>& str, bits& val);

} /* namespace seminumeric */

template <> class numeric_limits<seminumeric::integer>;

} /* namespace std */

Class integer

class integer {
public:

    // constructors
    integer();

    integer(char val);
    integer(signed char val);
    integer(unsigned char val);
    integer(short val);
    integer(unsigned short val);
    integer(int val);
    integer(unsigned val);
    integer(long val);
    integer(unsigned long val);
    integer(long long val);
    integer(unsigned long long val);

    integer(float val);
    integer(double val);
    integer(long double val);

    integer(std::initializer_list<uint_least32_t> init);

    template <class CharT, class Traits, class Alloc>
        explicit integer(const std::basic_string<CharT, Traits, Alloc>& str);

    integer(const integer& other);
    integer(integer&& other);
    explicit integer(const bits& val);
    explicit integer(bits&& val);

    // assignment and swap
    integer& operator=(const integer& rhs);
    integer& operator=(integer&& rhs);
    integer& operator=(const bits& rhs);
    integer& operator=(bits&& rhs);
    void swap(integer& other);

    // conversions
    explicit operator long long() const;
    explicit operator unsigned long long() const;
    explicit operator long double() const;
    explicit operator bool() const;

    // comparisons
    int compare(const integer& rhs) const;

    // arithmetic operations
    integer& operator+=(const integer& rhs);
    integer& operator-=(const integer& rhs);
    integer& operator*=(const integer& rhs);
    integer& operator/=(const integer& rhs);
    integer& operator%=(const integer& rhs);

    integer& operator++();
    integer operator++(int);
    integer& operator--();
    integer operator--(int);

    integer div(const integer& rhs);

    integer& abs();
    integer& negate();
    integer operator+() const;
    integer operator-() const;

    integer& operator<<=(int shift);
    integer& operator>>=(int shift);

    // numeric operations
    integer& sqr();
    integer& sqrt();
    integer& pow(const integer& exp);

    // observers
    bool is_odd() const;

    // accessors
    integer_data_proxy get_data_proxy();

};

The class describes an object that manages an unbounded-precision signed integral type that can be used in most contexts where an int could be used.

integer abs(const integer& other);
integer& integer::abs();

The first function returns an object that holds the absolute value lf other. The second function sets the stored value of *this to its absolute value and returns a reference to *this.

int integer::compare(const integer& right) const;

The member function returns a value less than 0 if *this is less than rhs, 0 if *this is equal to rhs, and greater than 0 if *this is greater than rhs.

std::pair<integer, integer> div(const integer& left, const integer& right);
std::pair<integer, integer> integer::div(const integer& right) const;

The functions return an object that is an instantiation of std::pair; its first field holds the quotient, left / right or *this / right, and its second field holds the remainder, left % right or *this % right.

integer_data_proxy integer::get_data_proxy();

The member function returns an object of type integer_data_proxy that can be used to examine and modify the internal storage of *this. If an object of type integer_data_proxy that refers to *this exists at the time of a call to this function, the function throws an exception object of type std::runtime_error.

integer::integer();

integer::integer(char val);
integer::integer(signed char val);
integer::integer(unsigned char val);
integer::integer(short val);
integer::integer(unsigned short val);
integer::integer(int val);
integer::integer(unsigned int val);
integer::integer(long val);
integer::integer(unsigned long val);
integer::integer(long long val);
integer::integer(unsigned long long val);

integer::integer(float val);
integer::integer(double val);
integer::integer(long double val);

integer::integer(std::initializer_list<unspecified> list);

template<class CharT, class Traits, class Alloc>
    explicit integer::integer(const std::basic_string<CharT, Traits, Alloc>& str);

integer::integer(const integer& other);
integer::integer(integer&& other);
integer::integer(const bits& other);
integer::integer(bits&& other);

The default constructor constructs an object whose value is 0.

The constructors that take integral arguments construct objects whose value is val.

The constructors that take floating-point arguments construct objects whose value is an approximation to val, accurate to at least std::numeric_limits::digits.

The constructor that takes a string constructs an object whose value is the value represented by the string object. The string object shall have the form required for the string argument to the function std::strtol with a radix of base, and shall be interpreted as if by std::strtol(str.c_str(), 0, base), except that the resulting value can never be outside the range of representable values.

The constructor that takes an initializer_list constructs an object whose stored value is equal to the elements of the initializer_list treated as a series of unsigned 32-bit digits with the leftmost digit being most significant. For example, the initializer list { 0xFE, 0xF0, 0xAA, 0x31 } represents the value 0xFE * 323 + 0xF0 * 322 + 0xAA * 321 + 0x31 * 320.

The copy and move constructors construct objects with the same value as other.

bool integer::is_odd() const;

The member function returns true only if the stored value represents an odd number.

integer& integer::negate();

The member function sets the stored value of *this to the negation of its previous vaue and returns a reference to *this.

integer& integer::operator=(const integer& right);
integer& integer::operator=(integer&& right);
integer& integer::operator=(const bits& right);
integer& integer::operator=(bits&& right);

The operators store the value of right into *this.

integer operator+(const integer& left, const integer& right);
integer integer::operator+() const;

The first operator returns an object whose value is the sum of the values of left and right. The second operator returns a copy of *this.

integer& integer::operator+=(const integer& right);

The member operator sets the stored value of *this to the sum of the values of *this and right and returns a reference to *this.

integer& integer::operator++();
integer integer::operator++(int);

The member operators set the value stored in *this to *this + 1. The first operator returns *this. The second operator returns an object whose value is the value stored in *this prior to the increment.

integer operator-(const integer& left, const integer& right)
integer integer::operator-();

The first operator returns an object whose value is the difference between the values of left and right. The second operator returns an object whose value is the negation of the value of *this.

integer& integer::operator-=(const integer&);

The member operator sets the stored value of *this to the difference between the values of *this and right and returns a reference to *this.

integer& integer::operator--();
integer integer::operator--(int);

The member operators set the value stored in *this to *this - 1. The first operator returns *this. The second operator returns an object whose value is the value stored in *this prior to the decrement.

integer operator*(const integer& left, const integer& right);

The operator returns an object whose value is the product of the values of left and right.

integer& integer::operator*=(const integer& right);

The member operator sets the stored value of *this to the product of the values of *this and right and returns a reference to *this.

integer operator/(const integer& left, const integer& right);

The operator returns an object whose value is the quotient of the value of left divided by the value of right, discarding any fractional part.

integer& integer::operator/=(const integer& right);

The member operator sets the stored value of *this to the quotient of the value of *this divided by the value of right, discarding any fractional part, and returns a reference to *this.

integer operator%(const integer&, const integer&);

The operator returns an object whose value is the remainder of the value of left divided by the value of right. The remainder is the value such that (left / right) * right + left % right is equal to left.

integer& integer::operator%=(const integer&);

The member operator sets the stored value of *this to the remainder of *this divided by the value of right and returns a reference to *this.

integer operator>>(const integer& val, int shift);

If the value of shift is negative, the operator returns operator<<(val, -shift). Otherwise, the operator returns a new object whose value is val / 2shift.

integer& integer::operator>>=(int);

If the value of shift is negative, the operator has the effect of *this <<= -shift. Otherwise, the operator sets the value of *this to *this / 2shift. The operator returns a reference to *this.

template <class Elem, class Traits>
    std::basic_istream<Elem, Traits>& operator>>(std::basic_istream<Elem, Traits>& strm, integer& val);

The operator has the effect of { std::string temp; strm >> temp; val = temp; }. It returns a reference to strm.

integer operator<<(const integer& val, int shift);

If the value of shift is negative, the operator returns operator>>(val, -shift). Otherwise, the operator returns a new object whose value is val * 2shift.

integer& integer::operator<<=(int shift);

If the value of shift is negative, the operator has the effect of *this >>= -shift. Otherwise, the operator sets the value of *this to *this * 2shift. The operator returns a reference to *this.

template <class Elem, class Traits>
    std::basic_ostream<Elem, Traits>& operator<<(std::basic_ostream<Elem, Traits>& strm, const integer& val);

The operator has the effect of strm << val.to_string(). It returns a reference to strm.

explicit integer::operator bool() const;

The operator returns false only if *this is equal to 0.

explicit integer::operator long double() const;

The operator returns a value equal to the stored value of *this.

explicit bits::operator long long() const;

The operator returns a value equal to the stored value of *this.

explicit bits::operator unsigned long long() const;

The operator returns a value equal to the stored value of *this.

bool operator==(const integer& left, const integer& right);

The operator returns true only if the value stored in left is equal to the value stored in right.

bool operator!=(const integer& left, const integer& right);

The operator returns !(left == right).

bool operator>(const integer& left, const integer& right);

The operator returns right < left.

bool operator>=(const integer& left, const integer& right);

The operator returns !(left < right).

bool operator<(const integer& left, const integer& right);

The operator return true only if left.compare(right) returns -1.

bool operator<=(const integer& left, const integer& right);

The operator returns !(right < left).

integer pow(const integer& val, const integer& exp);
integer& integer::pow(const integer& exp);

The non-member function returns an object whose value is valexp. The member function sets the value of *this to *thisexp and returns *this. Requires: 0 <= exp.

integer sqr(const integer& val);
integer& integer::sqr();

The non-member function returns an object whose value is val * val. The member function sets the value of *this to *this * *this and returns a reference to *this.

integer sqrt(const integer&);
integer& integer::sqrt();

The non-member function returns an object whose value is the square root of the value held by val, discarding any fractional part. The member function sets the value of *this to the square root of the value held by *this, discarding any fractional part, and returns a reference to *this. Requires: 0 <= exp.

void swap(integer& left, integer& right);
void integer::swap(integer& right);

The non-member function swaps the stored values of left and right. The member function swaps the stored values of *this and right.

std::string integer::to_string(int radix = 16) const;

The member function returns a string representation of the value stored in *this, using radix as the radix.

Class integer_data_proxy

class integer_data_proxy {

    // type names
    typedef unspecified data_type;
    typedef unspecified arithmetic_type;
    typedef unspecified uarithmetic_type;
    typedef unspecified size_type;
    typedef unspecified iterator;
    typedef unspecified const_iterator;
    typedef unspecified reverse_iterator;
    typedef unspecified const_reverse_iterator;

    // constructors
    integer_data_proxy(const integer_data_proxy& other) = delete;
    integer_data_proxy(integer_data_proxy&& other) = default;

    // assignment
    integer_data_proxy& operator=(const integer_data_proxy& rhs) = delete;
    integer_data_proxy& operator=(integer_data_proxy&& rhs) = default;

    // iterators
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;
    const_iterator cbegin() const;
    const_iterator cend() const;
    const_reverse_iterator crbegin() const;
    const_reverse_iterator crend() const;

    // capacity
    size_type size() const;
    void resize(size_type sz);

    // element access
    data_type operator[](size_type n) const;
    data_type& operator[](size_type n);

};

The class describes an object that can be used to examine and modify the internal representation of an object of type integer. This allows advanced users to portably implement algorithms that are not provided natively.

There can be only one integer_data_proxy object associated with a particular integer object at any given time; that object is obtained by calling the get_data_proxy member function on the integer object. The resulting object can be moved but not copied.

typedef unspecified integer_data:proxy::arithmetic_type;

The typedef defines a synonym for a signed arithmetic type with at least twice as many bits as the internal storage type.

iterator integer_data_proxy::begin();

The member function returns an iterator object such that the iterators [begin(), end()) point to the internal data elements of the integer object.

const_iterator integer_data_proxy::cbegin() const;

The member function returns an iterator object such that the iterators [cbegin(), cend()) point to the internal data elements of the integer object.

const_iterator integer_data_proxy::cend() const;

The member function returns an iterator object such that the iterators [cbegin(), cend()) point to the internal data elements of the integer object.

typedef unspecified integer_data_proxy::const_iterator;

The typedef defines a synonym for an iterator that can be used to access but not modify internal data elements of the integer object.

typedef unspecified integer_data_proxy::const_reverse_iterator;

The typedef defines a synonym for a reverse iterator that can be used to access but not modify internal data elements of the integer object.

const_reverse_iterator integer_data_proxy::crbegin() const;

The member function returns a reverse iterator object such that the iterators [crbegin(), crend()) point to the internal data elements of the integer object.

const_reverse_iterator integer_data_proxy::crend() const;

The member function returns a reverse iterator object such that the iterators [crbegin(), crend()) point to the internal data elements of the integer object.

typedef unspecified integer_data_proxy::data_type;

The typedef defines a synonym for the type of the integer object's internal data elements.

iterator integer_data_proxy::end();

The member function returns an iterator object such that the iterators [begin(), end()) point to the internal data elements of the integer object.

integer_data_proxy::integer_data_proxy(const integer_data_proxy&) = delete; 
integer_data_proxy::integer_data_proxy(integer_data_proxy&&) = delete;

The copy constructor and move constructor are deleted.

typedef unspecified integer_data_proxy::iterator;

The typedef defines a synonym for an iterator that can be used to access internal data elements of the integer object.

integer& integer_data_proxy::operator=(const integer_data_proxy&) = delete;
integer& integer_data_proxy::operator=(integer_data_proxy&&) = delete;

The copy assignment and move assignment operators are deleted.

data_type integer_data_proxy::operator[](size_type n) const;
data_type& integer_data_proxy::operator[](size_type n);

The first member function returns the value of the internal data element at index n. The second member function returns a reference to the value of the internal data element at index n.

const_reverse_iterator integer_data_proxy::rbegin() const;
reverse_iterator integer_data_proxy::rbegin();

The member functions return a reverse iterator object such that the iterators [crbegin(), crend()) point to the internal data elements of the integer object.

const_reverse_iterator integer_data_proxy::rend() const;
reverse_iterator integer_data_proxy::rend();

The member functions return a reverse iterator object such that the iterators [crbegin(), crend()) point to the internal data elements of the integer object.

void integer_data_proxy::resize(size_type sz);

The member function ensures that the integer object holds at least sz internal data elements.

typedef unspecified integer_data_proxy::reverse_iterator;

The typedef defines a synonym for a reverse iterator that can be used to access internal data elements of the integer object.

size_type integer_data_proxy::size() const;

The member function returns the number of internal data elements in the integer object.

typedef unspecified integer_data_proxy::size_type;

The typedef defines a synonym for an unsigned arithmetic type that can hold a count of the number of internal data elements in the integer object.

typedef unspecified integer_data:proxy::uarithmetic_type;

The typedef defines a synonym for an unsigned arithmetic type with at least twice as many bits as the internal storage type.

Class bits

class bits {
public:

    class reference;

    // constructors
    bits();

    bits(char val);
    bits(signed char val);
    bits(unsigned char val);
    bits(short val);
    bits(unsigned short val);
    bits(int val);
    bits(unsigned val);
    bits(long val);
    bits(unsigned long val);
    bits(long long val);
    bits(unsigned long long val);

    bits(const char *str);
    template <class CharT, class Traits, class Alloc>
    explicit bits(const basic_string<CharT, Traits, Alloc>& str,
        typename basic_string<CharT, Traits, Alloc>::size_type pos = 0,
        typename basic_string<CharT, Traits, Alloc>::size_type count = std::basic_string<CharT>::npos,
        CharT digit0 = CharT('0'),
        CharT digit1 = CharT('1'));
    template <class CharT>
    explicit bits(const CharT *ptr,
        typename basic_string<CharT>::size_type count = std::basic_string<CharT>::npos,
        CharT digit0 = CharT('0'),
        CharT digit1 = CharT('1'));

    bits(std::initializer_list<uint_least32_t> list);

    bits(const bits& other);
    bits(bits&& other);
    bits(const integer& val);
    bits(integer&& val);

    // assignment and swap
    bits& operator=(const bits& rhs);
    bits& operator=(bits&& rhs);
    bits& operator=(const integer& rhs);
    bits& operator=(integer&& rhs);
    void swap(bits& rhs);

    // conversions
    unsigned long to_ulong() const;
    unsigned long long to_ullong() const;
    template <class CharT = char, class Traits = std::char_traits<CharT>, class Alloc = std::allocator<CharT> >
        std::basic_string<CharT, Traits, Alloc> to_string(CharT zero = CharT('0'), CharT one = CharT('1'));

    // logical operations
    bits& operator&=(const bits& rhs);
    bits& operator|=(const bits& rhs);
    bits& operator^=(const bits& rhs);
    bits operator~() const;
    
    bits& operator<<=(size_type shift);
    bits& operator>>=(size_type shift);
    bits& operator<<(size_type shift) const;
    bits& operator>>(size_type shift) const;

    // element access and modification
    bits& set();
    bits& set(size_type pos, bool val = true);
    bits& reset();
    bits& reset(size_type pos);
    bits& flip();
    bits& flip(size_type pos);
    bool operator[](size_type pos) const;
    reference operator[](size_type pos);
    bool test(size_type pos) const;
    bool all() const;
    bool any() const;
    bool none() const;
    size_type lowest_bit() const;
    size_type highest_bit() const;
    size_type count() const;

    // capacity
    size_type size() const;
    void resize(size_type sz);

};

The class describes an object that represents an unbounded set of bits.

bool all() const

The member function returns true only if all the bits in *this are set.

bool any() const

The member function returns true if at least one of the bits in *this is set.

bits::bits();

bits::bits(char val);
bits::bits(signed char val);
bits::bits(unsigned char val);
bits::bits(short val);
bits::bits(unsigned short val);
bits::bits(int val);
bits::bits(unsigned int val);
bits::bits(long val);
bits::bits(unsigned long val);
bits::bits(long long val);
bits::bits(unsigned long long val);

bits::bits(const char *str);
template <class CharT, class Traits, class Alloc>
explicit bits::bits(const basic_string<CharT, Traits, Alloc>& str,
    typename basic_string<CharT, Traits, Alloc>::size_type pos = 0,
    typename basic_string<CharT, Traits, Alloc>::size_type count = std::basic_string<CharT>::npos,
    CharT digit0 = CharT('0'),
    CharT digit1 = CharT('1'));
template <class CharT>
explicit bits::bits(const CharT *ptr,
    typename basic_string<CharT>::size_type count = std::basic_string<CharT>::npos,
    CharT digit0 = CharT('0'),
    CharT digit1 = CharT('1'));

bits::bits(std::initializer_list<uint_least32_t> list);

bits::bits(const bits& other);
bits::bits(bits&& other);
explicit bits::bits(const integer& other);
explicit bits::bits(integer&& other);

The default constructor constructs an object whose value is 0.

The constructors that take integral arguments construct objects whose value is val; negative values construct an object whose value is the complement of bits(abs(val)).

The constructors that take string and const char* objects construct an object whose value is the value represented by their argument, treating zero as 0 and one as 1.

The constructor that takes an initializer_list constructs an object whose stored value is equal to the elements of the initializer_list treated as a series of unsigned 32-bit digits with the leftmost digit being most significant. For example, the initializer list { 0xFE, 0xF0, 0xAA, 0x31 } represents the value 0xFE * 323 + 0xF0 * 322 + 0xAA * 321 + 0x31 * 320.

The copy and move constructors construct objects with the same value as other; the move constructors leave other in an unspecified valid state. Construction from a negative integer value constructs an object whose value is the complement of bits(abs(val)).

size_type count() const;

The member function returns the number of bits in *this that are set.

void bits::flip(size_t pos);

The member function toggles the bit at position pos in the stored value.

int bits::highest_bit() const;

The member function returns the zero-based position of the highest non-zero bit in the stored value, or -1 if there are no non-zero bits.

int bits::lowest_bit() const;

The member function returns the zero-based position of the lowest non-zero bit in the stored value, or -1 if there are no non-zero bits.

bool none() const;

The member function returns true only if none of the bits in *this is set.

bits& bits::operator=(const bits& right);
bits& bits::operator=(bits&& right);
bits& bits::operator=(const unsigned_bits& right);
bits& bits::operator=(unsigned_bits&& right);

The operators store the value of right into *this.

bits operator&(const bits& left, const bits& right);

The operator returns an object whose value is the bitwise AND of the values of left and right.

bits& bits::operator&=(const bits& right);

The member operator sets the value of *this to the bitwise AND of the values of *this and right and returns a reference to *this.

bits operator|(const bits& left, const bits& right);

The operator returns an object whose value is the bitwise inclusive OR of the values of left and right.

bits& bits::operator|=(const bits& right);

The member operator sets the value of *this to the bitwise inclusive OR of the values of *this and right and returns a reference to *this.

bits operator^(const bits& left, const bits& right);

The operator returns an object whose value is the bitwise exclusive OR of the values of left and right.

bits& bits::operator^=(const bits& right);

The member operator sets the value of *this to the bitwise exclusive OR of the values of *this and right and returns a reference to *this.

bits operator~() const;

The member function returns an object that holds the complement of the set of bits held by *this.

bits operator>>(const bits& val, int shift);

If the value of shift is negative, the operator returns operator<<(val, -shift). Otherwise, the operator returns a new object whose stored value is the value of the bits in *this shifted right shift positions.

bits& bits::operator>>=(int shift);

If the value of shift is negative, the operator returns val << -shift. Otherwise, the operator sets the stored value in *this to the value of the bits in *this shifted right shift positions.

template <class CharT, class Traits>
    std::basic_istream<CharT, Traits>& operator>>(
        std::basic_istream<CharT, Traits>& str, bits& val);

The operator has the effect of { std::string temp; strm >> temp; val = temp; } and returns a reference to strm.

bits operator<<(const bits& val, int shift);

If the value of shift is negative, the operator returns operator>>(val, -shift). Otherwise, the operator returns a new object whose stored value is the value of the bits in *this shifted left shift positions.

bits& bits::operator<<=(int shift);

If the value of shift is negative, the operator returns val >> -shift. Otherwise, the operator sets the stored value in *this to the value of the bits in *this shifted left shift positions.

template <class CharT, class Traits>
    std::basic_ostream<CharT, Traits>& operator<<(
        std::basic_ostream<CharT, Traits>& str, const bits& val);

The operator has the effect of strm << val.to_string() and returns a reference to strm.

bool operator[](size_type pos) const;
reference operator[](size_type pos);

The first member function returns the value of the bit at position pos. The second member function returns an object of type bits::reference that refers to the bit at position pos.

bits& reset();
bits& reset(size_type pos);

The first member function clears all the bits of *this. The second member function clears the bit as position pos.

void resize(size_type sz);

The member function adjusts the storage capacity of*this so that it can hold at least sz bits without reallocating.

void bits::set();
void bits::set(size_t pos, bool val = true);

The first member function sets all the bits of *this. The second member function sets the bit at position pos in the stored value to val.

size_type size() const;

The member function returns the maximum number of bits that can be held in *this without reallocating.

void swap(bits& left, bits& right);
void bits::swap(bits& right);

The non-member function swaps the stored values of left and right. The member function swaps the stored values of *this and right.

bool bits::test(size_t pos) const;

The member function returns true only if the bit at position pos in the stored value is non-zero.

template <class CharT = char, class Traits = std::char_traits<CharT>, class Alloc = std::allocator<CharT> >
    std::basic_string<CharT, Traits, Alloc> bits::to_string(
        CharT zero = CharT('0'), CharT one = CharT('1'));

The member function returns a string representation of the value stored in *this, using zero to represent 0 and one to represent 1.

unsigned long long bits::to_ullong() const;

The member function returns a value equal to the stored value of *this.

unsigned long bits::to_ulong() const;

The member function returns a value equal to the stored value of *this.

Class bits::reference

class bits {
    class reference {
    public:
        reference& operator=(bool val);
        reference& operator=(const reference& rhs);
        bool operator~() const;
        operator bool() const;
        reference& flip();
    };
};

The nested class bits::reference describes an object that can be used to manage a particular bit in an object of type bits.

reference& bits::reference::flip();

The member function toggles the bit that the object manages.

reference& bits::reference::operator=(bool right);
reference& bits::reference::operator=(const reference& right);

The first member operator sets the bit that the object manages to the value of right. The second member operator sets the bit that the object manages to the value managed by right.

bool bits::reference::operator~() const;

The member operator returns true if the bit managed by the object is set, otherwise false.

bits::reference::operator bool() const;

The member operator returns true if the bit that the object manages is set.