Integer Utilities

Description

The library provides utility functions for safe integer types. These operate on the non-bounded unsigned types (u8, u16, u32, u64, u128).

#include <boost/safe_numbers/integer_utilities.hpp>

isqrt

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto isqrt(const T val) -> T;

Returns the integer square root of val, i.e., the largest integer r such that r * r <= val.

Uses Newton’s method on the underlying hardware type. The computation cannot overflow and converges rapidly.

Parameters

val — The value to compute the integer square root of.

Return Value

The floor of the square root of val, as the same safe integer type T.

Complexity

O(log(val)) iterations of Newton’s method.

Example

using namespace boost::safe_numbers;

auto r = isqrt(u32{100});   // r == u32{10}
auto s = isqrt(u32{200});   // s == u32{14}  (floor of sqrt(200))
auto t = isqrt(u32{0});     // t == u32{0}
auto u = isqrt(u32{1});     // u == u32{1}

remove_trailing_zeros

Removes trailing decimal zeros from an unsigned integer value using a branchless algorithm based on modular multiplicative inverses (Granlund-Montgomery division).

Return Type

template <typename UInt>
struct remove_trailing_zeros_return
{
    UInt trimmed_number;
    std::size_t number_of_removed_zeros;
};

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto remove_trailing_zeros(const T n);

Removes all trailing decimal zeros from n. Returns a remove_trailing_zeros_return containing the trimmed value and the count of removed zeros, such that trimmed_number * 10^number_of_removed_zeros == n.

Parameters

n — The value to remove trailing zeros from. If n is zero, returns {0, 0}.

Return Value

A remove_trailing_zeros_return where:

trimmed_number is n with all trailing decimal zeros removed.
number_of_removed_zeros is the count of removed zeros.

Supported Types and Ranges

Type	Max Trailing Zeros	Algorithm Steps
`u8`	2	2
`u16`	4	3
`u32`	9	4
`u64`	19	5
`u128`	38	6

Example

using namespace boost::safe_numbers;

auto r1 = remove_trailing_zeros(u32{12300});
// r1.trimmed_number == 123, r1.number_of_removed_zeros == 2

auto r2 = remove_trailing_zeros(u64{1000000});
// r2.trimmed_number == 1, r2.number_of_removed_zeros == 6

auto r3 = remove_trailing_zeros(u8{static_cast<std::uint8_t>(7)});
// r3.trimmed_number == 7, r3.number_of_removed_zeros == 0

is_power_10

Tests whether an unsigned integer value is an exact power of 10 (i.e., one of 1, 10, 100, 1000, …).

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto is_power_10(const T n) -> bool;

Parameters

n — The value to test.

Return Value

true if n is a power of 10, false otherwise.

Example

using namespace boost::safe_numbers;

is_power_10(u32{1000});      // true
is_power_10(u32{1});         // true
is_power_10(u32{1234});      // false
is_power_10(u64{10000000000000000000ULL});  // true

ilog2

Returns the integer base-2 logarithm (floor of log₂) of a value.

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto ilog2(const T n) -> int;

Computes floor(log₂(n)) using bit_width(n) - 1.

Parameters

n — The value to compute the logarithm of. Must be non-zero.

Throws

std::domain_error if n == 0.

Return Value

The floor of the base-2 logarithm of n.

Complexity

O(1).

Example

using namespace boost::safe_numbers;

auto r1 = ilog2(u32{1024});   // r1 == 10  (2^10 = 1024)
auto r2 = ilog2(u32{1000});   // r2 == 9   (floor of log2(1000))
auto r3 = ilog2(u32{1});      // r3 == 0
auto r4 = ilog2(u64{9223372036854775808ULL});  // r4 == 63  (2^63)

ilog10

Returns the integer base-10 logarithm (floor of log₁₀) of a value.

Uses an O(1) algorithm based on the most significant bit position to approximate log₁₀, refined with a single power-of-10 table lookup.

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto ilog10(const T n) -> int;

Computes floor(log₁₀(n)) using num_digits(n) - 1, where num_digits approximates the digit count via log₁₀(x) ~= log₂(x) / log₂(10) and refines with at most two comparisons against a power-of-10 lookup table.

Parameters

n — The value to compute the logarithm of. Must be non-zero.

Throws

std::domain_error if n == 0.

Return Value

The floor of the base-10 logarithm of n.

Example

using namespace boost::safe_numbers;

auto r1 = ilog10(u32{1000});        // r1 == 3
auto r2 = ilog10(u32{999});         // r2 == 2   (floor of log10(999))
auto r3 = ilog10(u32{1});           // r3 == 0
auto r4 = ilog10(u64{10000000000000000000ULL});  // r4 == 19

ilog

Returns the integer logarithm in an arbitrary base (floor of log_base) of a value.

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto ilog(const T n, const T base) -> int;

Computes floor(log_base(n)) by repeated division. For the common cases of base 2 and base 10, prefer the specialized ilog2 and ilog10 functions which run in O(1).

Parameters

n — The value to compute the logarithm of. Must be non-zero.
base — The base of the logarithm. Must be >= 2.

Throws

std::domain_error if n == 0.
std::domain_error if base < 2 (base 0 would cause division by zero; base 1 would cause an infinite loop).

Return Value

The floor of the base-base logarithm of n. For n < base, returns 0.

Complexity

O(log_base(n)) divisions.

Example

using namespace boost::safe_numbers;

auto r1 = ilog(u32{1000}, u32{10});    // r1 == 3   (floor of log10(1000))
auto r2 = ilog(u32{1024}, u32{2});     // r2 == 10  (floor of log2(1024))
auto r3 = ilog(u32{80}, u32{3});       // r3 == 3   (floor of log3(80))
auto r4 = ilog(u32{3125}, u32{5});     // r4 == 5   (5^5 = 3125)
auto r5 = ilog(u32{1}, u32{7});        // r5 == 0   (any base, log(1) = 0)

ipow

Integer exponentiation using the exponentiation-by-squaring algorithm.

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto ipow(const T a, const T b) noexcept -> T;

Computes a raised to the power b using exponentiation by squaring.

The algorithm runs in O(log(b)) multiplications:

If b == 0, returns T{1}.
If b is odd, returns a * ipow(a, b - 1).
If b is even, returns ipow(a, b / 2)^2.

If the result overflows the type, the behavior follows the overflow policy of the safe integer type (by default, throwing std::overflow_error).

Parameters

a — The base value.
b — The exponent value.

Return Value

a raised to the power b, as the same safe integer type T.

Complexity

O(log(b)) multiplications.

Example

using namespace boost::safe_numbers;

auto r1 = ipow(u32{2}, u32{10});     // r1 == u32{1024}
auto r2 = ipow(u32{10}, u32{9});     // r2 == u32{1000000000}
auto r3 = ipow(u64{3}, u64{30});     // r3 == u64{205891132094649}
auto r4 = ipow(u32{5}, u32{0});      // r4 == u32{1}

is_power_2

Tests whether an unsigned integer value is an exact power of 2 (i.e., has exactly one bit set).

template <non_bounded_unsigned_library_type T>
[[nodiscard]] constexpr auto is_power_2(const T n) noexcept -> bool;

Parameters

n — The value to test.

Return Value

true if n is a power of 2, false otherwise.

Example

using namespace boost::safe_numbers;

is_power_2(u32{1024});     // true
is_power_2(u32{1});        // true
is_power_2(u32{1000});     // false
is_power_2(u64{9223372036854775808ULL});  // true  (2^63)

abs_diff

Computes the absolute difference between two integers without risk of underflow. For unsigned types, naive subtraction a - b when b > a would underflow; abs_diff always returns the non-negative distance between the two values.

template <integral_library_type T>
[[nodiscard]] constexpr auto abs_diff(const T a, const T b) noexcept -> T;

Returns |a - b|, computed as a - b if a >= b, or b - a otherwise.

Works with all safe integer types: u8, u16, u32, u64, u128, and bounded_uint<Min, Max>.

Parameters

a — The first value.
b — The second value.

Return Value

The absolute difference between a and b, as the same safe integer type T. The result is always commutative: abs_diff(a, b) == abs_diff(b, a).

Complexity

O(1).

Example

using namespace boost::safe_numbers;

auto r1 = abs_diff(u32{10}, u32{3});      // r1 == u32{7}
auto r2 = abs_diff(u32{3}, u32{10});      // r2 == u32{7}  (commutative)
auto r3 = abs_diff(u32{42}, u32{42});     // r3 == u32{0}
auto r4 = abs_diff(u32{0}, u32{100});     // r4 == u32{100}

div_ceil

Computes the ceiling of integer division, i.e., the smallest integer not less than the exact quotient a / b. For unsigned types, this is equivalent to (a + b - 1) / b but computed without risk of overflow.

template <integral_library_type T>
[[nodiscard]] constexpr auto div_ceil(const T a, const T b) noexcept -> T;

Returns the ceiling of a / b. When a is evenly divisible by b, returns a / b. Otherwise, returns a / b + 1.

Works with all safe integer types: u8, u16, u32, u64, u128, and bounded_uint<Min, Max>.

Parameters

a — The dividend.
b — The divisor. Must not be zero.

Return Value

The smallest integer greater than or equal to the exact quotient a / b, as the same safe integer type T.

Complexity

O(1).

Example

using namespace boost::safe_numbers;

auto r1 = div_ceil(u32{10}, u32{3});      // r1 == u32{4}   (ceil(3.33) = 4)
auto r2 = div_ceil(u32{9}, u32{3});       // r2 == u32{3}   (exact division)
auto r3 = div_ceil(u32{0}, u32{5});       // r3 == u32{0}
auto r4 = div_ceil(u32{1}, u32{2});       // r4 == u32{1}   (ceil(0.5) = 1)
auto r5 = div_ceil(u32{100}, u32{100});   // r5 == u32{1}

next_multiple_of

Computes the smallest multiple of b that is greater than or equal to a. This is useful for alignment calculations (e.g., aligning a size to a page boundary or block size).

template <integral_library_type T>
[[nodiscard]] constexpr auto next_multiple_of(const T a, const T b) noexcept -> T;

Returns the smallest value m such that m >= a and m % b == 0. Equivalent to div_ceil(a, b) * b.

Works with all safe integer types: u8, u16, u32, u64, u128, and bounded_uint<Min, Max>.

Parameters

a — The value to round up.
b — The alignment / divisor. Must not be zero.

Return Value

The smallest multiple of b that is greater than or equal to a, as the same safe integer type T. When a is already a multiple of b, returns a. When a == 0, returns 0.

Complexity

O(1).

Example

using namespace boost::safe_numbers;

auto r1 = next_multiple_of(u32{10}, u32{3});      // r1 == u32{12}   (next multiple of 3 >= 10)
auto r2 = next_multiple_of(u32{9}, u32{3});        // r2 == u32{9}    (already a multiple)
auto r3 = next_multiple_of(u32{0}, u32{5});        // r3 == u32{0}
auto r4 = next_multiple_of(u32{1}, u32{4096});     // r4 == u32{4096} (align to page size)
auto r5 = next_multiple_of(u32{4097}, u32{4096});  // r5 == u32{8192}

Edit this Page