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

log2

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

template <non_bounded_unsigned_library_type T>
[[nodiscard]] 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)

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.

template <non_bounded_unsigned_library_type T>
[[nodiscard]] 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) ~= 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

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}
Edit this Page