bi::bi_t Class Reference

Arbitrary-precision integer type and related functions. More...

#include "bi.hpp"

Public Member Functions
	bi_t () noexcept
	Default constructor. The integer is initialized to zero and no memory allocation occurs.
template<std::integral T>
	bi_t (T)
	Constructor for integral types.
	bi_t (const bi_t &)
	Copy constructor.
	bi_t (bi_t &&other) noexcept
	Move constructor. After the move, other is left in a valid state representing the integer 0.
Construct from a string
Construct an integer from a string representing a base-base integer. These are explicit constructors. Exceptions std::invalid_argument Throws if a parsing error occurs, if a null pointer is provided, or if an invalid base is provided. Allows leading whitespace and/or a plus/minus sign before the first base-base digit. base must be an integer in \( [2, 36] \) (by default, it is 10). Examples: bi_t a{"98765"}; // 98765 bi_t b{"-98765"}; // -98765 bi_t c{" -6789"}; // -6789 bi_t empty{""}; // Throws std::invalid_argument bi_t nll{nullptr}; // Throws std::invalid_argument bi_t invalid{" -"}; // Throws std::invalid_argument
	bi_t (const std::string &, int base=10)
	bi_t (const char *, int base=10)
	bi_t (double)
Assignment operators
bi_t &	operator= (const bi_t &)
	Copy assignment operator.
bi_t &	operator= (bi_t &&other) noexcept
	Move assignment operator. After the move, other is left in a valid state representing the integer 0.
template<std::integral T>
bi_t &	operator= (T)
	Assign a builtin integral type value to a bi_t.
bi_t &	operator= (const std::string &)
bi_t &	operator= (const char *)
bi_t &	operator= (double)
Unary operators
bi_t	operator+ () const
bi_t	operator- () const
Increment and decrement
bi_t &	operator++ ()
bi_t	operator++ (int)
bi_t &	operator-- ()
bi_t	operator-- (int)
Multiplicative operators
Exceptions bi::division_by_zero Throws if a division by zero attempt is detected.
bi_t	operator* (const bi_t &) const
bi_t	operator/ (const bi_t &) const
bi_t	operator% (const bi_t &) const
bi_t &	operator*= (const bi_t &)
bi_t &	operator/= (const bi_t &)
bi_t &	operator%= (const bi_t &)
std::pair< bi_t, bi_t >	div (const bi_t &) const
	Computes both the quotient and remainder of division of this bi_t object by another bi_t object and returns both the quotient and the remainder as a pair.
Additive operators
bi_t	operator+ (const bi_t &) const
bi_t	operator- (const bi_t &) const
bi_t &	operator+= (const bi_t &)
bi_t &	operator-= (const bi_t &)
Shift operators
Note Prior to the C++20 Standard, the behavior of << and >> is undefined or implementation-defined if the left operand is negative. In contrast, the C++20 Standard defines the behavior of << and >> for both negative and nonnegative left operands. This implementation conforms to the C++20 Standard (except for any wrap-around behavior, as the bi_t is not a fixed-width integer) and makes the result of << equivalent to \( x \times 2^{shift} \) and the result of >> equivalent to \( \left\lfloor \frac{x}{2^{\text{shift}}} \right\rfloor \). Parameters shift An unsigned long representing the number of bit positions to shift by.
bi_t	operator<< (bi_bitcount_t shift) const
	Return a new integer representing the integer left-shifted shift bit positions with vacated bits zero-filled.
bi_t	operator>> (bi_bitcount_t shift) const
	Return a new integer representing the integer right-shifted shift bit positions. This is an arithmetic right shift with sign extension.
bi_t &	operator<<= (bi_bitcount_t shift)
bi_t &	operator>>= (bi_bitcount_t shift)
Comparisons
std::strong_ordering	operator<=> (const bi_t &) const noexcept
bool	operator== (const bi_t &) const noexcept
Comparisons with integral types
Efficient comparison between bi_ts and any standard integral type T, with no implicit conversions from Ts to bi_ts (and hence no memory allocation).
template<std::integral T>
std::strong_ordering	operator<=> (T) const noexcept
template<std::integral T>
bool	operator== (T) const noexcept
Comparisons with floats
Compare a bi_t to a floating-point number. These member functions handle the case where a bi_t is on the left-hand side (LHS) and a double is on the right-hand side (RHS). There are also non-member functions that facilitate comparisons where the double is on the LHS. These comparisons are designed to be consistent with IEEE 754, handling special cases like NaNs and infinities. NaN: Operators ==, <, <=, >, and >= return false when comparing with NaN. Operator != returns true when comparing with NaN. Infinities: Positive infinity is treated as greater than any bi_t number. Negative infinity is treated as less than any bi_t number. Note The spaceship operator (<=>) is not used here due to the unordered nature of NaN in IEEE 754. Instead, each comparison operator is explicitly defined to handle NaN appropriately. In comparisons of bi_ts with bi_ts and bi_ts with integral types, the spaceship operator is used, which, combined with operator==, implicitly allows comparisons using ==, !=, <, <=, >, and >=, both when a bi_t is on the LHS and on the RHS. Here, in order to handle NaN appropriately, we explicitly define all of ==, !=, <, <=, >, and >=, both for when a bi_t is on the LHS and RHS.
bool	operator== (double) const noexcept
bool	operator!= (double) const noexcept
bool	operator< (double) const noexcept
bool	operator<= (double) const noexcept
bool	operator> (double) const noexcept
bool	operator>= (double) const noexcept
Bitwise operators
Note These operators perform bitwise operations on integers using two's complement representation (with sign extension).
bi_t	operator~ () const
	Unary complement operator. Return a new integer representing the ones' complement of this integer.
bi_t	operator& (const bi_t &) const
bi_t	operator| (const bi_t &) const
bi_t	operator^ (const bi_t &) const
bi_t &	operator&= (const bi_t &)
bi_t &	operator|= (const bi_t &)
bi_t &	operator^= (const bi_t &)
Conversion operators
	operator bool () const noexcept
	true if and only if this integer is nonzero.
template<std::integral T>
	operator T () const noexcept
	Converts a bi_t object to an integral type T.
	operator double () const noexcept
Bits
bi_bitcount_t	bit_length () const noexcept
	If nonzero, return the number of bits required to represent its absolute value. Otherwise (i.e. the integer is zero), return 0.
bool	test_bit (bi_bitcount_t) const noexcept
	Test bit i, acting as if the integer is nonnegative.
bi_t &	set_bit (bi_bitcount_t)
	Set bit i, acting as if the integer is nonnegative, but preserving its original sign in the result.
Accessors for internal representation
size_t	capacity () const noexcept
	Return the number of digits the allocated storage can hold.
size_t	size () const noexcept
	Return the number of digits used. Instance represents 0 iff size() == 0.
bool	negative () const noexcept
	Return true if the integer is (strictly) negative, false otherwise.
std::span< const digit >	digits () const
	Return a read-only span of the digits stored in the internal digit vector, with least significant digits first. If the integer is zero, an empty span is returned.
void	print_internal (std::ostream &os=std::cout) const noexcept
Other
void	swap (bi_t &) noexcept
	Swap the contents of this bi_t object with another bi_t object.
std::string	to_string (int base=10) const
	Return a string containing the base-base representation of the integer, where base must be an integer in \( [2, 36] \) (by default, base is 10).
void	negate () noexcept
	Negates the integer in place.
int	sign () const noexcept
	Return an int indicating the sign of the number: -1 for negative, 0 for zero, 1 for positive.
bool	odd () const noexcept
	Return true if this integer is odd, false otherwise.
bool	even () const noexcept
	Return true if this integer is even, false otherwise.
template<std::integral T>
bool	within () const noexcept
	Return true if this integer fits in an integral type T, false otherwise.

Static Public Member Functions
Exponentiation
static bi_t	pow (const bi_t &base, bi_bitcount_t exp)
static bi_t	pow (const bi_t &base, const bi_t &exp)

Friends
std::ostream &	operator<< (std::ostream &os, const bi_t &x)
	Outputs the base-10 (decimal) representation of a bi_t object to a standard output stream.
bool	operator== (double lhs, const bi_t &rhs) noexcept
bool	operator!= (double lhs, const bi_t &rhs) noexcept
bool	operator< (double lhs, const bi_t &rhs) noexcept
bool	operator<= (double lhs, const bi_t &rhs) noexcept
bool	operator> (double lhs, const bi_t &rhs) noexcept
bool	operator>= (double lhs, const bi_t &rhs) noexcept

Related Symbols
(Note that these are not member symbols.)
void	swap (bi_t &a, bi_t &b) noexcept
	Swap the contents of a with b.
bi_t	operator""_bi (const char *s)
	User-defined literal (UDL) operator for creating bi_t objects.
bi_t	abs (const bi_t &value)
	Return a new integer representing the absolute value of the argument integer.

Detailed Description

Arbitrary-precision integer type and related functions.

An instance of bi_t represents an arbitrary precision integer.

The implementation has several design goals, including, but not limited to:

1. Memory safety, through the use of smart pointers or standard library containers.
2. Strong exception safety. Some operations may throw, but if they do, original values should remain intact.

Exceptions

std::bad_alloc	Throws in case of memory allocation failure.
bi::overflow_error	Throws if an operation expects the result to require a digit vector with size() exceeding max_size(). See internals below.
bi::division_by_zero	Throws if a division by zero attempt is detected.
bi::from_float	Throws when attempting to convert a NaN or infinity to a bi_t.
std::invalid_argument	Throws in a string constructor if an invalid string or argument is provided.

The custom exception classes derive from std::runtime_error. To catch and handle these specific exceptions, #include the "bi_exceptions.hpp" header (in addition to "bi.hpp").

Internals

The representation of a bi_t consists of a digit vector and a boolean indicating if the integer is negative. The integer is represented internally as a base \( 2^{n} \) integer where \( n \) is typically 32 bits. An element of the digit vector, i.e. a digit, is typically a uint32_t. The digit vector stores the magnitude of the integer, with least significant digits first. Counts of bits are represented by the bi_bitcount_t type, which is an unsigned long. Counts of bytes for dynamically allocated memory expects a size_t type. Thus, the digit vector is theoretically constrained to be less than or equal to SIZE_MAX / sizeof(digit). Additionally, because counts of bits use the unsigned long type, we also constrain the maximum size of the vector to be less than or equal to ULONG_MAX / (CHAR_BIT * sizeof(digit)), where the denominator is the number of bits in the digit data type (typically 32). Together, these constraints determine max_size() for the internal digit vector. An operation that expects a result to exceed max_size() throws bi::overflow_error.

Constructor & Destructor Documentation

bi_t()

bi::bi_t::bi_t ( )

noexcept

Default constructor. The integer is initialized to zero and no memory allocation occurs.

Complexity

O(1)

Member Function Documentation

capacity()

size_t bi::bi_t::capacity ( ) const

noexcept

Return the number of digits the allocated storage can hold.

Complexity

O(1)

digits()

std::span< const digit > bi::bi_t::digits

(

)

const

Return a read-only span of the digits stored in the internal digit vector, with least significant digits first. If the integer is zero, an empty span is returned.

Warning

Modifying the integer after the span is returned may invalidate the span.

Complexity

O(1)

div()

std::pair< bi_t, bi_t > bi::bi_t::div

(

const bi_t &

other

)

const

Computes both the quotient and remainder of division of this bi_t object by another bi_t object and returns both the quotient and the remainder as a pair.

Parameters

other

The divisor.

Returns

A pair of bi_t objects where the first element is the quotient and the second element is the remainder.

Complexity

\( O(m \cdot n) \) where \( m \) is the size() of the dividend and \( n \) is the size() of the divisor.

even()

bool bi::bi_t::even ( ) const

noexcept

Return true if this integer is even, false otherwise.

Complexity

O(1)

negate()

void bi::bi_t::negate ( )

noexcept

Negates the integer in place.

Complexity

O(1)

negative()

bool bi::bi_t::negative ( ) const

noexcept

Return true if the integer is (strictly) negative, false otherwise.

Complexity

O(1)

odd()

bool bi::bi_t::odd ( ) const

noexcept

Return true if this integer is odd, false otherwise.

Complexity

O(1)

operator bool()

bi::bi_t::operator bool ( ) const

explicitnoexcept

true if and only if this integer is nonzero.

Example:

bi_t x;
if (x) {
  std::cout << "x is nonzero!" << std::endl;
} else {
  std::cout << "x is zero!" << std::endl;
}

The output is

x is zero!

Complexity

O(1)

operator T()

template<std::integral T>

bi::bi_t::operator T ( ) const

explicitnoexcept

Converts a bi_t object to an integral type T.

As with the C++20 Standard (7.3.8, p. 93):

‍[T]he result is the unique value of the destination type that is congruent to the source integer modulo \( 2^{N} \), where \( N \) is the width of the destination type.

operator!=()

bool bi::bi_t::operator!= ( double other ) const

noexcept

Complexity

O(1)

operator%()

bi_t bi::bi_t::operator%

(

const bi_t &

other

)

const

Complexity

\( O(m \cdot n) \)

operator%=()

bi_t & bi::bi_t::operator%=

(

const bi_t &

other

)

Complexity

\( O(m \cdot n) \)

operator&()

bi_t bi::bi_t::operator&

(

const bi_t &

other

)

const

Mathematically, given two integers \( x, y \) with coefficients \( x_{i}, y_{i} \) of their binary representation, the result of \( x \; \& \; y \) (bitwise AND) is an integer \( r \) with base-2 coefficients \( r_{i} \) such that

\[ r_{i} = 1 \Longleftrightarrow x_{i} = 1 \wedge y_{i} = 1 \]

operator*()

bi_t bi::bi_t::operator*

(

const bi_t &

other

)

const

Complexity

\( O(n^{\log_{2}(3)}) \approx O(n^{1.58}) \)

operator*=()

bi_t & bi::bi_t::operator*=

(

const bi_t &

other

)

Complexity

\( O(n^{\log_{2}(3)}) \approx O(n^{1.58}) \)

operator+()

bi_t bi::bi_t::operator+

(

const bi_t &

other

)

const

Complexity

\( O(n) \)

operator+=()

bi_t & bi::bi_t::operator+=

(

const bi_t &

other

)

Complexity

\( O(n) \)

operator-()

bi_t bi::bi_t::operator-

(

const bi_t &

other

)

const

Complexity

\( O(n) \)

operator-=()

bi_t & bi::bi_t::operator-=

(

const bi_t &

other

)

Complexity

\( O(n) \)

operator/()

bi_t bi::bi_t::operator/

(

const bi_t &

other

)

const

Complexity

\( O(m \cdot n) \)

operator/=()

bi_t & bi::bi_t::operator/=

(

const bi_t &

other

)

Complexity

\( O(m \cdot n) \)

operator<()

bool bi::bi_t::operator< ( double other ) const

noexcept

Complexity

O(1)

operator<<()

bi_t bi::bi_t::operator<<

(

bi_bitcount_t

shift

)

const

Return a new integer representing the integer left-shifted shift bit positions with vacated bits zero-filled.

Mathematically, the value of the resulting integer is

\[ x \times 2^{\text{shift}} \]

where \( x \) is the big integer.

operator<=()

bool bi::bi_t::operator<= ( double other ) const

noexcept

Complexity

O(1)

operator==()

bool bi::bi_t::operator== ( double other ) const

noexcept

Complexity

O(1)

operator>()

bool bi::bi_t::operator> ( double other ) const

noexcept

Complexity

O(1)

operator>=()

bool bi::bi_t::operator>= ( double other ) const

noexcept

Complexity

O(1)

operator>>()

bi_t bi::bi_t::operator>>

(

bi_bitcount_t

shift

)

const

Return a new integer representing the integer right-shifted shift bit positions. This is an arithmetic right shift with sign extension.

Mathematically, the value of the resulting integer is \( \frac{x}{2^{\text{shift}}} \), rounded down:

\[ \left\lfloor \frac{x}{2^{\text{shift}}} \right\rfloor \]

where \( x \) is the big integer.

operator^()

bi_t bi::bi_t::operator^

(

const bi_t &

other

)

const

Mathematically, given two integers \( x, y \) with coefficients \( x_{i}, y_{i} \) of their binary representation, the result of \( x \; ^\wedge \; y \) (bitwise exclusive OR) is an integer \( r \) with base-2 coefficients \( r_{i} \) such that

\[ r_{i} = 1 \Longleftrightarrow (x_{i} = 1 \wedge y_{i} = 0) \lor (x_{i} = 0 \wedge y_{i} = 1) \]

operator|()

bi_t bi::bi_t::operator|

(

const bi_t &

other

)

const

Mathematically, given two integers \( x, y \) with coefficients \( x_{i}, y_{i} \) of their binary representation, the result of \( x \; | \; y \) (bitwise inclusive OR) is an integer \( r \) with base-2 coefficients \( r_{i} \) such that

\[ r_{i} = 1 \Longleftrightarrow x_{i} = 1 \lor y_{i} = 1 \]

print_internal()

void bi::bi_t::print_internal ( std::ostream & os = std::cout ) const

noexcept

Prints the integer in the form

(d_p * 2**(bi_dbits * p) + ... + d_0 * 2**(bi_dbits * 0))

followed by a newline. Outputs to the specified std::ostream or to standard output (std::cout) by default. If the integer is negative, the output will be preceded by a minus sign (-). bi_dbits is typically 32.

Useful for understanding the internal representation of the integer.

Parameters

os	The output stream to which the internal representation is printed. If not specified, defaults to standard output (std::cout).

Complexity

O(n)

sign()

int bi::bi_t::sign ( ) const

noexcept

Return an int indicating the sign of the number: -1 for negative, 0 for zero, 1 for positive.

Complexity

O(1)

size()

size_t bi::bi_t::size ( ) const

noexcept

Return the number of digits used. Instance represents 0 iff size() == 0.

Complexity

O(1)

swap()

void bi::bi_t::swap ( bi_t & other )

noexcept

Swap the contents of this bi_t object with another bi_t object.

Complexity

O(1)

to_string()

std::string bi::bi_t::to_string

(

int

base = 10

)

const

Return a string containing the base-base representation of the integer, where base must be an integer in \( [2, 36] \) (by default, base is 10).

Examples:

bi_t x;
std::string s = x.to_string();  // s == "0"
x = 65535;
s = x.to_string();              // s == "65535"
x = -32768;
s = x.to_string();              // s == "-32768"

within()

template<std::integral T>

bool bi::bi_t::within ( ) const

noexcept

Return true if this integer fits in an integral type T, false otherwise.

For bi_t object x and integral type T, x.within<T>() evaluates to

x >= std::numeric_limits<T>::min() && x <= std::numeric_limits<T>::max()

Example:

bi_t x = std::numeric_limits<int32_t>::max();
bool fits_in_int32 = x.within<int32_t>();  // true
bool fits_in_int16 = x.within<int16_t>();  // false

Friends And Related Symbol Documentation

operator""_bi()

bi_t operator""_bi ( const char * s )

related

User-defined literal (UDL) operator for creating bi_t objects.

Returns

bi_t(s).

Example:

// Equivalent to bi_t fib{"123581321345589144"};
bi_t fib = 123581321345589144_bi;

operator<<

std::ostream & operator<< ( std::ostream & os, const bi_t & x )

friend

Outputs the base-10 (decimal) representation of a bi_t object to a standard output stream.

This overload of the stream insertion operator allows instances of bi_t to be sent to standard output streams like std::cout. The bi_t object is converted to a string via to_string() before being output.

Parameters

os	The output stream to which the data is sent.
x	The bi_t object to be output.

Returns

A reference to the output stream, to support chaining of << operators.

swap()

void swap ( bi_t & a, bi_t & b )

related

Swap the contents of a with b.

Complexity

O(1)