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) and their verified counterparts.

#include <boost/safe_numbers/integer_utilities.hpp>

isqrt

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
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}

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto isqrt(const verified_type_basis<T> val) -> verified_type_basis<T>;

Compile-time only overload for verified types. Delegates to the runtime overload after extracting the basis value, and wraps the result back into a verified type.

Since isqrt is consteval for verified types, the result is guaranteed to be a compile-time constant.

Example

using namespace boost::safe_numbers;

constexpr auto r = isqrt(verified_u32{u32{144}});  // r == verified_u32{u32{12}}
constexpr auto s = isqrt(verified_u64{u64{1000000}});  // s == verified_u64{u64{1000}}

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;
};

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
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.

The algorithm is entirely branchless (no data-dependent branches), operating via modular inverse multiplication and bit rotation. It processes the exponent in O(log(max_digits)) steps, where max_digits is the maximum number of decimal digits for the type.

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

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto remove_trailing_zeros(const verified_type_basis<T> val);

Compile-time-only overload for verified types. Delegates to the detail implementation after extracting the underlying value.

Since remove_trailing_zeros is consteval for verified types, the result is guaranteed to be a compile-time constant.

Example

using namespace boost::safe_numbers;

constexpr auto r = remove_trailing_zeros(verified_u32{u32{5000}});
// r.trimmed_number == 5, r.number_of_removed_zeros == 3

is_power_10

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

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
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

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto is_power_10(const verified_type_basis<T> n) -> bool;

Compile-time-only overload for verified types.

Since is_power_10 is consteval for verified types, the result is guaranteed to be a compile-time constant and can be used directly in static_assert.

Example

using namespace boost::safe_numbers;

static_assert(is_power_10(verified_u32{u32{100}}));
static_assert(!is_power_10(verified_u32{u32{200}}));

log2

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

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
constexpr auto log2(const T n) noexcept -> int;

Computes floor(log2(n)) using bit_width(n) - 1.

Parameters

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

Return Value

The floor of the base-2 logarithm of n. For n == 0, returns -1 (since bit_width(0) == 0).

Complexity

O(1).

Example

using namespace boost::safe_numbers;

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

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto log2(const verified_type_basis<T> n) noexcept -> int;

Compile-time only overload for verified types.

Since log2 is consteval for verified types, the result is guaranteed to be a compile-time constant.

Example

using namespace boost::safe_numbers;

static_assert(log2(verified_u32{u32{1048576}}) == 20);    // 2^20
static_assert(log2(verified_u64{u64{9223372036854775808ULL}}) == 63);

log10

Returns the integer base-10 logarithm (floor of log10) of a value.

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

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
constexpr auto log10(const T n) noexcept -> int;

Computes floor(log10(n)) using num_digits(n) - 1, where num_digits approximates the digit count via log10(x) ~{equals} log2(x) / log2(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.

Return Value

The floor of the base-10 logarithm of n.

Example

using namespace boost::safe_numbers;

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

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto log10(const verified_type_basis<T> n) noexcept -> int;

Compile-time only overload for verified types.

Since log10 is consteval for verified types, the result is guaranteed to be a compile-time constant.

Example

using namespace boost::safe_numbers;

static_assert(log10(verified_u32{u32{1000000000}}) == 9);
static_assert(log10(verified_u64{u64{10000000000000000000ULL}}) == 19);

ipow

Integer exponentiation using the exponentiation-by-squaring algorithm.

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
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}

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto ipow(const verified_type_basis<T> a, const verified_type_basis<T> b) -> verified_type_basis<T>;

Compile-time only overload for verified types. Returns a verified type, preserving the compile-time guarantee.

Since ipow is consteval for verified types, the computation is guaranteed to occur at compile time. Overflow produces a compile error.

Example

using namespace boost::safe_numbers;

constexpr auto r = ipow(verified_u32{u32{2}}, verified_u32{u32{20}});  // r == verified_u32{u32{1048576}}
constexpr auto s = ipow(verified_u64{u64{10}}, verified_u64{u64{18}}); // s == verified_u64{u64{1000000000000000000}}

is_power_2

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

Runtime Overload

template <non_bounded_unsigned_library_type T>
    requires (!is_verified_type_v<T>)
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)

Verified Overload

template <non_bounded_unsigned_library_type T>
consteval auto is_power_2(const verified_type_basis<T> n) noexcept -> bool;

Compile-time-only overload for verified types.

Since is_power_2 is consteval for verified types, the result is guaranteed to be a compile-time constant and can be used directly in static_assert.

Example

using namespace boost::safe_numbers;

static_assert(is_power_2(verified_u32{u32{1048576}}));   // 2^20
static_assert(!is_power_2(verified_u32{u32{1000000}}));
Edit this Page