Arithmetic & Logic Operations

Header aarith/integer/integer_operations.hpp

namespace aarith

Functions

template<typename I, typename T> constexpr auto expanding_add(const I &a, const T &b, const bool initial_carry)

Adds two unsigned integers of, possibly, different bit widths.

Template Parameters

I – Integer type of the first summand
T – Integer type of the second summand

Parameters

a – First summand
b – Second summand
initial_carry – True if there is an initial carry coming in

Returns

Sum of a and b with bit width max(I::width,T::width)+1

template<typename I, typename T> constexpr auto expanding_add(const I &a, const T &b)

template<typename I> constexpr auto sub(const I &a, const I &b) -> I 

Computes the difference of two integers.

Template Parameters

I – The integer type used in the subtraction

Parameters

a – Minuend
b – Subtrahend

Returns

Difference between a and b

template<typename I, typename T> constexpr auto expanding_sub(const I &a, const T &b)

Subtracts two integers of, possibly, different bit widths.

Expanding does not, in contrast to

See also

expanding_add, ensure that no underflow will happen. It simply makes sure that the resulting bit width is the larger of both input bit widths.

Template Parameters

W – Width of the minuend
V – Width of the subtrahend

Parameters

a – Minuend
b – Subtrahend

Returns

Difference of correct bit width

template<typename I> I constexpr add(const I &a, const I &b)

Adds two integers.

Template Parameters

I – The integer type used for the addition

Parameters

a – First summand
b – Second summand

Returns

Sum of a and b

template<std::size_t W, std::size_t V, typename WordType> constexpr uinteger<W + V, WordType> schoolbook_expanding_mul(const uinteger<W, WordType> &a, const uinteger<V, WordType> &b)

Multiplies two unsigned integers expanding the bit width so that the result fits.

This implements the simplest multiplication algorithm (binary “long multiplication”) that adds up the partial products everywhere where the first multiplicand has a 1 bit. The simplicity, of course, comes at the cost of performance.

Template Parameters

W – The bit width of the first multiplicand
V – The bit width of the second multiplicand

Parameters

a – First multiplicand
b – Second multiplicand

Returns

Product of a and b

template<typename I, typename = std::enable_if_t<is_integral_v && is_unsigned_v>> constexpr I schoolbook_mul(const I &a, const I &b)

Multiplies two integers.

The result is then cropped to fit the initial bit width

See also

booth_expanding_mul for that.

Note

No Type conversion is performed. If the bit widths do not match, the code will not compile! Use

Template Parameters

I – The integer type to operate on

Parameters

a – First multiplicand
b – Second multiplicand

Returns

Product of a and b

template<std::size_t W, std::size_t V, typename WordType> constexpr uinteger<W + V, WordType> expanding_karazuba(const uinteger<W, WordType> &a, const uinteger<V, WordType> &b)

Multiplies two unsigned integers using the Karazuba algorithm expanding the bit width so that the result fits.

This implements the karazuba multiplication algorithm (divide and conquer).

Template Parameters

W – The bit width of the first multiplicant
V – The bit width of the second multiplicant

Parameters

a – First multiplicant
b – Second multiplicant

Returns

Product of a and b

template<std::size_t W, std::size_t V, typename WordType> constexpr std::pair<uinteger<W, WordType>, uinteger<W, WordType>> restoring_division(const uinteger<W, WordType> &numerator, const uinteger<V, WordType> &denominator)

Implements the restoring division algorithm.

Parameters

numerator – The number that is to be divided
denominator – The number that divides the other number

Template Parameters

W – Width of the numbers used in division.

Returns

Pair of (quotient, remainder)

template<typename I> constexpr auto remainder(const I &numerator, const I &denominator) -> I 

Computes the remainder of the division of one integer by another integer.

Note

For signed integers, weird under-/overflows for ::min() may occur

Template Parameters

I – Integer type to work on

Parameters

numerator – The number that is to be divided
denominator – The number that divides the other number

Returns

The remainder of the division operation

template<typename I> constexpr auto div(const I &numerator, const I &denominator) -> I 

Divides one integer by another integer.

Note

integer<W>::min/integer<W>(-1) will return <integer<W>::min,0>, i.e. some weird overflow happens for signed integers

Template Parameters

I – Integer type to work on

Parameters

numerator – The number that is to be divided
denominator – The number that divides the other number

Returns

The quotient of the division operation

template<size_t Width, typename WordType> constexpr auto abs(const integer<Width, WordType> &n) -> integer<Width, WordType>

Computes the absolute value of a given signed integer.

There is a potential loss of precision as abs(integer::min) > integer::max

Template Parameters: Width – The width of the signed integer
Parameters: n – The signed inter to be “absolute valued”
Returns: The absolute value of the signed integer

template<size_t Width, typename WordType> constexpr auto expanding_abs(const integer<Width, WordType> &n) -> uinteger<Width, WordType>

Computes the absolute value of a given signed integer.

This method returns an unsigned integer. This means that the absolute value will fit and no overflow will happen.

Template Parameters: Width – The width of the signed integer
Parameters: n – The signed inter to be “absolute valued”
Returns: The absolute value of the signed integer

template<class IntA, class IntB> constexpr auto fun_add_expand(const IntA &a, const IntB &b, const bool initial_carry = false)

Adds two signed integers of, possibly, different bit widths.

This is an implementation using a more functional style of programming. It is not particularly fast and only here for educational purposes. You can use method as a means to understand how to work on an integer.

Template Parameters

IntA – The integer type of the first summand
IntB – The integer type of the second summand

Parameters

a – First summand
b – Second summand
initial_carry – True if there is an initial carry coming in

Returns

Sum of correct maximal bit width

template<typename I> constexpr auto fun_add(const I &a, const I &b, const bool initial_carry = false) -> I 

Adds two integers of, possibly, different bit widths.

See also

fun_add_expand

Template Parameters

I – Integer type used in the addition

Parameters

a – First summand
b – Second summand
initial_carry – True if there is an initial carry coming in

Returns

Sum of a and b

template<size_t Width, typename WordType> auto constexpr operator>>=(integer<Width, WordType> &lhs, const size_t rhs) -> integer<Width, WordType>

Arithmetic right-shift operator.

This shift preserves the signedness of the integer.

Template Parameters

Width – The width of the signed integer

Parameters

lhs – The integer to be shifted
rhs – The number of bits to be shifted

Returns

The shifted integer

template<size_t Width, typename WordType, typename U, typename = std::enable_if_t<is_unsigned_v>> auto constexpr operator>>=(integer<Width, WordType> &lhs, const U &rhs) -> integer<Width, WordType>&

template<size_t Width, typename WordType> auto constexpr operator>>(const integer<Width, WordType> &lhs, const size_t rhs) -> integer<Width, WordType>

Arithmetic right-shift operator.

This shift preserves the signedness of the integer.

Template Parameters

Width – The width of the signed integer

Parameters

lhs – The integer to be shifted
rhs – The number of bits to be shifted

Returns

The shifted integer

template<size_t Width, typename WordType, typename U, typename = std::enable_if_t<is_unsigned_v>> auto constexpr operator>>(const integer<Width, WordType> &lhs, const U &rhs) -> integer<Width, WordType>

template<typename I, typename = std::enable_if_t<is_integral_v>> I &operator--(I &a)

template<typename I, typename = std::enable_if_t<is_integral_v>> I operator--(I &a, int)

template<typename I, typename = std::enable_if_t<is_integral_v>> I &operator++(I &a)

template<typename I, typename = std::enable_if_t<is_integral_v>> I operator++(I &a, int)

template<size_t W, size_t V, typename WordType> constexpr auto naive_expanding_mul(const integer<W, WordType> &m, const integer<V, WordType> &r)

Naively multiplies two signed integers.

Template Parameters

W – The bit width of the first multiplicand
V – The bit width of the second multiplicand

Parameters

a – First multiplicand
b – Second multiplicand

Returns

Product of a and b

template<size_t W, typename WordType> constexpr integer<W, WordType> naive_mul(const integer<W, WordType> &a, const integer<W, WordType> &b)

Naively multiplies two integers.

The result is then cropped to fit the initial bit width

See also

booth_expanding_mul for that.

Note

No Type conversion is performed. If the bit widths do not match, the code will not compile! Use

Template Parameters

I – The integer type to operate on

Parameters

a – First multiplicand
b – Second multiplicand

Returns

Product of a and b

template<size_t x, size_t y, typename WordType> constexpr auto booth_expanding_mul(const integer<x, WordType> &m, const integer<y, WordType> &r) -> integer<y + x, WordType>

Multiplies two signed integers.

This implements the Booth multiplication algorithm with extension to correctly handle the most negative number. See https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm for details.

Template Parameters

x – The bit width of the first multiplicant
y – The bit width of the second multiplicant

Parameters

m – Multiplicand
r – Multiplier

Returns

Product of m and r

template<size_t W, typename WordType> constexpr integer<W, WordType> booth_mul(const integer<W, WordType> &a, const integer<W, WordType> &b)

Multiplies two integers.

The result is then cropped to fit the initial bit width

See also

booth_expanding_mul for that.

Note

No Type conversion is performed. If the bit widths do not match, the code will not compile! Use

Template Parameters

I – The integer type to operate on

Parameters

a – First multiplicand
b – Second multiplicand

Returns

Product of a and b

template<size_t x, size_t y, typename WordType> constexpr auto booth_inplace_expanding_mul(const integer<x, WordType> &m, const integer<y, WordType> &r) -> integer<y + x, WordType>

Multiplies two signed integers.

This implements the Booth multiplication algorithm with extension to correctly handle the most negative number. See https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm for details.

Template Parameters

x – The bit width of the first multiplicant
y – The bit width of the second multiplicant

Parameters

m – Multiplicand
r – Multiplier

Returns

Product of m and r

template<size_t W, typename WordType> constexpr integer<W, WordType> booth_inplace_mul(const integer<W, WordType> &a, const integer<W, WordType> &b)

Multiplies two integers.

The result is then cropped to fit the initial bit width

See also

booth_expanding_mul for that.

Note

No Type conversion is performed. If the bit widths do not match, the code will not compile! Use

Template Parameters

I – The integer type to operate on

Parameters

a – First multiplicand
b – Second multiplicand

Returns

Product of a and b

template<size_t W, typename WordType> constexpr auto negate(const integer<W, WordType> &n) -> integer<W, WordType>

Negates the value.

Template Parameters: W – The width of the signed integer
Parameters: n – The signed integer whose sign is to be changed
Returns: The negative value of the signed integer

template<size_t W, typename WordType> constexpr int8_t signum(integer<W, WordType> n)

Computes the sign of the integer.

For the number zero, the function returns a signum of 0, -1 for negative numbers and +1 for positive numbers.

Template Parameters

W – The width of the integer
WordType – The word type to store the data in

Parameters

n – The integer

Returns

The sign of the integer

template<size_t W, typename WordType> constexpr int8_t signum(uinteger<W, WordType> n)

Computes the sign of the unsigned integer.

For the number zero, the function returns a signum of 0 and a 1 for every other number.

Template Parameters: W – The width of the unsigned integer
Parameters: n – The integer
Returns: The sign of the integer

template<std::size_t W, std::size_t V, typename WordType> constexpr std::pair<integer<W, WordType>, integer<W, WordType>> restoring_division(const integer<W, WordType> &numerator, const integer<V, WordType> &denominator)

Implements the restoring division algorithm.

Note

integer<W>::min/integer<W>(-1) will return <integer<W>::min,0>, i.e. some weird overflow happens

Parameters

numerator – The number that is to be divided
denominator – The number that divides the other number

Template Parameters

W – Width of the numbers used in division.

Returns

Pair of (quotient, remainder)

template<typename I, typename = std::enable_if_t<is_integral_v>> constexpr I mul(const I &a, const I &b)

template<typename I, typename = std::enable_if_t<is_integral_v>> auto constexpr expanding_mul(const I &a, const I &b)

template<typename IntegerType> IntegerType pow(const IntegerType &base, const size_t exponent)

Exponentiation function.

Note

This function does not make any attempts to be fast or to prevent overflows!

Note

If exponent equals std::numeric_limits<size_t>::max(), this method throws an exception, unless base equals zero

Template Parameters

W – Bit width of the integer

Parameters

base –
exponent –

Returns

The base to the power of the exponent

template<typename IntegerType> IntegerType pow(const IntegerType &base, const IntegerType &exponent)

Exponentiation function.

Note

This function does not make any attempts to be fast or to prevent overflows!

Note

If exponent equals std::numeric_limits<IntegerType>::max(), this method throws an exception, unless base equals zero

Template Parameters

IntegerType – The type of integer used in the computation

Parameters

base –
exponent –

Returns

The base to the power of the exponent

template<std::size_t W, typename WordType> constexpr uinteger<W, WordType> karazuba(const uinteger<W, WordType> &a, const uinteger<W, WordType> &b)

Multiplies two unsigned integers using the Karazuba algorithm.

This implements the karazuba multiplication algorithm (divide and conquer).

Template Parameters

W – The bit width of the multiplicants

Parameters

a – First multiplicant
b – Second multiplicant

Returns

Product of a and b

template<typename Integer> constexpr Integer distance(const Integer &a, const Integer &b)

Computes the distance (i.e. the absolute difference) between two integers.

Template Parameters

Integer – The integer type to operate on

Parameters

a – First integer
b – Second integer

Returns

The distance between the two integers

template<typename W, typename I, typename = std::enable_if_t<is_word_array_v<W> && is_integral_v && is_unsigned_v>> constexpr auto operator>>=(W &lhs, const I rhs) -> W 

Left-shift assignment operator.

Template Parameters

W – The word_container type to work on

Parameters

lhs – The word_container to be shifted
rhs – The number of bits to shift

Returns

The shifted word_container

template<typename W, typename I, typename = std::enable_if_t<is_word_array_v<W> && is_integral_v && is_unsigned_v>> constexpr auto operator>>(const W &lhs, const I rhs) -> W 

Left-shift assignment operator.

Template Parameters

W – The word_container type to work on

Parameters

lhs – The word_container to be shifted
rhs – The number of bits to shift

Returns

The shifted word_container

namespace integer_operators

Convenience namespace to include when code should be written the “normal” way. There is one caveat though: No automatic type conversion will take place!

Functions

template<typename I, typename = std::enable_if_t<is_integral::value>> auto constexpr operator-(const I &num) -> I 

template<typename I, typename = std::enable_if_t<is_integral::value>> auto constexpr operator+(const I &lhs, const I &rhs) -> I 

template<typename I, typename = std::enable_if_t<is_integral::value>> auto constexpr operator-(const I &lhs, const I &rhs) -> I 

template<typename I, typename = std::enable_if_t<is_integral_v>> auto constexpr operator*(const I &lhs, const I &rhs) -> I 

template<typename I, typename = std::enable_if_t<is_integral::value>> auto constexpr operator/(const I &lhs, const I &rhs) -> I 

template<typename I, typename = std::enable_if_t<is_integral::value>> auto constexpr operator%(const I &lhs, const I &rhs) -> I 