int_math.hpp

Go to the documentation of this file.

/*
 * Author: Sven Gothel <sgothel@jausoft.com>
 * Copyright (c) 2020-2024 Gothel Software e.K.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
 
#ifndef JAU_INT_MATH_HPP_
#define JAU_INT_MATH_HPP_
 
#include <bit>
#include <climits>
#include <cmath>
#include <concepts>
 
#include <jau/base_math.hpp>
#include <jau/int_math_ct.hpp>
#include <jau/type_concepts.hpp>
 
namespace jau {
 
    /** \addtogroup Integer
     *
     *  @{
     */
 
    /**
     * base_math: arithmetic types, i.e. integral + floating point types
     * int_math: integral types
     * float_math: floating point types
    // *************************************************
    // *************************************************
    // *************************************************
     */
 
    // Remember: constexpr specifier used in a function or static data member (since C++17) declaration implies inline.
 
    /** Returns true of the given integer value is zero. */
    template<std::integral T>
    constexpr bool is_zero(const T& a) noexcept {
        return 0 == a;
    }
 
    /**
     * Returns true if both values are equal.
     *
     * @tparam T an integral type
     * @param a value to compare
     * @param b value to compare
     */
    template<std::integral T>
    constexpr bool equals(const T& a, const T& b) noexcept {
        return a == b;
    }
 
    /**
     * Returns true if both values are equal, i.e. their absolute delta <= `allowed_deviation`.
     *
     * @tparam T an integral type
     * @param a value to compare
     * @param b value to compare
     * @param allowed_deviation allowed deviation
     */
    template<std::integral T>
    constexpr bool equals(const T& a, const T& b, const T& allowed_deviation) noexcept {
        return std::abs(a - b) <= allowed_deviation;
    }
 
    /**
     * Round up w/ branching in O(1)
     *
     * @tparam T an unsigned integral number type
     * @tparam U an unsigned integral number type
     * @param n to be aligned number
     * @param align_to alignment boundary, must not be 0
     * @return n rounded up to a multiple of align_to
     */
    template<jau::req::unsigned_integral T, jau::req::unsigned_integral U>
    constexpr T round_up(const T n, const U align_to) {
        assert(align_to != 0);  // align_to must not be 0
 
        if ( n % align_to ) {
            return n + (align_to - (n % align_to));
        } else {
            return n;
        }
    }
 
    /**
     * Round down w/ branching in O(1)
     *
     * @tparam T an unsigned integral number type
     * @tparam U an unsigned integral number type
     * @param n to be aligned number
     * @param align_to alignment boundary
     * @return n rounded down to a multiple of align_to
     */
    template<jau::req::unsigned_integral T, jau::req::unsigned_integral U>
    constexpr T round_down(T n, U align_to) {
        return align_to == 0 ? n : (n - (n % align_to));
    }
 
    /**
     * Power of 2 test in O(1), i.e. test whether a single bit is set
     *
     * Uses either
     * - C++20: std::has_single_bit
     * - else: [bithacks Test PowerOf2](http://www.graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
     *   - Branching may occur due to relational operator.
     *
     * @tparam T an unsigned integral number type
     * @param x the unsigned integral number
     * @return true if arg is 2^n for some x > 0
     * @see std::has_single_bit()
     */
    template<jau::req::unsigned_integral T>
    constexpr bool is_power_of_2(const T x) noexcept {
        if constexpr ( is_cxx20() ) {
            return std::has_single_bit(x);
        } else {
            return x && 0 == (x & (x - 1));
        }
    }
 
    /**
     * Returns log2(bytesize*8), e.g. to bit-shift whole byte values
     *
     * If bytesize is not of power2, zero is returned.
     *
     * @param bytesize number of bytes
     * @return log2(bytesize*8)
     */
    constexpr size_t log2_byteshift(const size_t bytesize) noexcept {
        if ( bytesize < 256 ) {
            switch ( bytesize ) {
                case 1:   return 3;   //    8 bits
                case 2:   return 4;   //   16 bits
                case 4:   return 5;   //   32 bits
                case 8:   return 6;   //   64 bits
                case 16:  return 7;   //  128 bits
                case 32:  return 8;   //  256 bits
                case 64:  return 9;   //  512 bits
                case 128: return 10;  // 1024 bits
                default:  return 0;   // non pow-2 bytesize
            }
        }
        if( !jau::is_power_of_2(bytesize) ) {
            return 0;
        }
        // starting w/ bytesize 256, shift 11
        size_t bitsize = (bytesize * 8) >> 11, r = 11;
        while ( bitsize >>= 1 ) {
            ++r;
        }
        return r;
    }
 
    /**
     * If the given {@code n} is not is_power_of_2() return next_power_of_2(),
     * otherwise return {@code n} unchanged.
     *
     * Uses either
     * - C++20: std::bit_ceil
     * - else: is_power_of_2 and ct_next_power_of_2
     *
     * @see std::bit_ceil()
     */
    template<jau::req::unsigned_integral T>
    constexpr T bit_ceil(const T n) noexcept {
        if constexpr ( is_cxx20() ) {
            return std::bit_ceil(n);
        } else if ( is_power_of_2(n) ) {
            return n;
        } else {
            return ct_next_power_of_2(n);
        }
    }
 
    /**
     * Return the index of the highest set bit w/ branching (loop) in O(n/2).
     *
     * @tparam T an unsigned integral number type
     * @param x value
     */
    template<jau::req::unsigned_integral T>
    constexpr nsize_t high_bit(T x) {
        nsize_t hb = 0;
        for ( nsize_t s = (CHAR_BIT * sizeof(T)) >> 1; s > 0; s >>= 1 ) {
            const nsize_t z = s * ((~jau::ct_is_zero(x >> s)) & 1);
            hb += z;
            x >>= z;
        }
        return hb + x;
    }
 
    /**
     * Returns the number of set bits within given unsigned integral
     *
     * @tparam T an unsigned integral number type
     * @param n value
     */
    template<jau::req::unsigned_integral T>
    constexpr size_t bit_count(T n) noexcept {
        return (size_t)std::popcount(n);
    }
 
    /**
     * Query whether `__builtin_add_overflow` is available
     * via `__has_builtin(__builtin_add_overflow)`.
     */
    consteval_cxx20 bool has_builtin_add_overflow() noexcept {
        #if defined __has_builtin && __has_builtin(__builtin_add_overflow)
            return true;
        #else
            return false;
        #endif
    }
    /**
     * Query whether `__builtin_sub_overflow` is available
     * via `__has_builtin(__builtin_sub_overflow)`.
     */
    consteval_cxx20 bool has_builtin_sub_overflow() noexcept {
        #if defined __has_builtin && __has_builtin(__builtin_sub_overflow)
            return true;
        #else
            return false;
        #endif
    }
    /**
     * Query whether `__builtin_mul_overflow` is available
     * via `__has_builtin(__builtin_mul_overflow)`.
     */
    consteval_cxx20 bool has_builtin_mul_overflow() noexcept {
        #if defined __has_builtin && __has_builtin(__builtin_mul_overflow)
            return true;
        #else
            return false;
        #endif
    }
 
    /**
     * Integer overflow aware addition returning true if overflow occurred,
     * otherwise false having the result stored in res.
     *
     * Implementation uses [Integer Overflow Builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
     * if available, otherwise its own implementation.
     *
     * @tparam T an integral integer type
     * @tparam
     * @param a operand a
     * @param b operand b
     * @param res storage for result
     * @return true if overflow, otherwise false
     */
    template<std::integral T>
    constexpr bool add_overflow(const T a, const T b, T& res) noexcept {
        if constexpr ( has_builtin_add_overflow() ) {
            return __builtin_add_overflow(a, b, &res);
        } else {
            // overflow:  a + b > R+ -> a > R+ - b, with b >= 0
            // underflow: a + b < R- -> a < R- - b, with b < 0
            if ( (b >= 0 && a > std::numeric_limits<T>::max() - b) ||
                 (b < 0 && a < std::numeric_limits<T>::min() - b) ) {
                return true;
            } else {
                res = a + b;
                return false;
            }
        }
    }
 
    /**
     * Integer overflow aware subtraction returning true if overflow occurred,
     * otherwise false having the result stored in res.
     *
     * Implementation uses [Integer Overflow Builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
     * if available, otherwise its own implementation.
     *
     * @tparam T an integral integer type
     * @tparam
     * @param a operand a
     * @param b operand b
     * @param res storage for result
     * @return true if overflow, otherwise false
     */
    template<std::integral T>
    constexpr bool sub_overflow(const T a, const T b, T& res) noexcept {
        if constexpr ( has_builtin_sub_overflow() ) {
            return __builtin_sub_overflow(a, b, &res);
        } else {
            // overflow:  a - b > R+ -> a > R+ + b, with b < 0
            // underflow: a - b < R- -> a < R- + b, with b >= 0
            if ( (b < 0 && a > std::numeric_limits<T>::max() + b) ||
                 (b >= 0 && a < std::numeric_limits<T>::min() + b) ) {
                return true;
            } else {
                res = a - b;
                return false;
            }
        }
    }
 
    /**
     * Integer overflow aware multiplication returning true if overflow occurred,
     * otherwise false having the result stored in res.
     *
     * Implementation uses [Integer Overflow Builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html)
     * if available, otherwise its own implementation.
     *
     * @tparam T an integral integer type
     * @tparam
     * @param a operand a
     * @param b operand b
     * @param res storage for result
     * @return true if overflow, otherwise false
     */
    template<std::integral T>
    constexpr bool mul_overflow(const T a, const T b, T& res) noexcept {
        if constexpr ( has_builtin_mul_overflow() ) {
            return __builtin_mul_overflow(a, b, &res);
        } else {
            // overflow: a * b > R+ -> a > R+ / b
            if ( (b > 0 && abs(a) > std::numeric_limits<T>::max() / b) ||
                 (b < 0 && abs(a) > std::numeric_limits<T>::min() / b) ) {
                return true;
            } else {
                res = a * b;
                return false;
            }
        }
    }
 
    /**
     * Returns the greatest common divisor (GCD) of the two given integer values following Euclid's algorithm from Euclid's Elements ~300 BC,
     * using the absolute positive value of given integers.
     *
     * Returns zero if a and b is zero.
     *
     * Note implementation uses modulo operator `(a/b)*b + a % b = a `,
     * i.e. remainder of the integer division - hence implementation uses `abs(a) % abs(b)`
     * in case the integral T is a signed type (dropped for unsigned).
     *
     * Implementation is similar to std::gcd(), however, it uses a fixed common type T
     * and a while loop instead of compile time evaluation via recursion.
     *
     * @tparam T integral type
     * @tparam
     * @param a integral value a
     * @param b integral value b
     * @return zero if a and b are zero, otherwise the greatest common divisor (GCD) of a and b,
     */
    template<jau::req::signed_integral T>
    constexpr T gcd(T a, T b) noexcept {
        T a_ = abs(a);
        T b_ = abs(b);
        while ( b_ != 0 ) {
            const T t = b_;
            b_ = a_ % b_;
            a_ = t;
        }
        return a_;
    }
 
    template<jau::req::unsigned_integral T>
    constexpr T gcd(T a, T b) noexcept {
        while ( b != 0 ) {
            const T t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
 
    /**
     * Integer overflow aware calculation of least common multiple (LCM) following Euclid's algorithm from Euclid's Elements ~300 BC.
     * @tparam T integral type
     * @tparam
     * @param result storage for lcm result: zero if a and b are zero, otherwise lcm of a and b
     * @param a integral value a
     * @param b integral value b
     * @return true if overflow, otherwise false for success
     */
    template<std::integral T>
    constexpr bool lcm_overflow(const T a, const T b, T& result) noexcept {
        const T _gcd = gcd<T>(a, b);
        if ( 0 < _gcd ) {
            T r;
            if ( mul_overflow(a, b, r) ) {
                return true;
            } else {
                result = r / _gcd;
                return false;
            }
        } else {
            result = 0;
            return false;
        }
    }
 
    /**
     * Returns the number of decimal digits of the given integral value number using std::log10<T>().<br>
     * If sign_is_digit == true (default), treats a potential negative sign as a digit.
     * <pre>
     * x < 0: 1 + (int) ( log10( -x ) ) + ( sign_is_digit ? 1 : 0 )
     * x = 0: 1
     * x > 0: 1 + (int) ( log10(  x ) )
     * </pre>
     * Implementation uses jau::invert_sign() to have a safe absolute value conversion, if required.
     * <p>
     * Convenience method, reusing precomputed sign of value to avoid redundant computations.
     * </p>
     * @tparam T an integral integer type
     * @param x the integral integer
     * @param x_sign the pre-determined sign of the given value x
     * @param sign_is_digit if true and value is negative, adds one to result for sign. Defaults to true.
     * @return digit count
     */
    template<std::integral T>
    constexpr size_t digits10(const T x, const snsize_t x_sign, const bool sign_is_digit = true) noexcept {
        if ( x_sign == 0 ) {
            return 1;
        }
        if ( x_sign < 0 ) {
            return 1 + static_cast<size_t>(std::log10<T>(invert_sign<T>(x))) + (sign_is_digit ? 1 : 0);
        } else {
            return 1 + static_cast<size_t>(std::log10<T>(x));
        }
    }
 
    /**
     * Returns the number of decimal digits of the given integral value number using std::log10<T>().
     * If sign_is_digit == true (default), treats a potential negative sign as a digit.
     * <pre>
     * x < 0: 1 + (int) ( log10( -x ) ) + ( sign_is_digit ? 1 : 0 )
     * x = 0: 1
     * x > 0: 1 + (int) ( log10(  x ) )
     * </pre>
     * Implementation uses jau::invert_sign() to have a safe absolute value conversion, if required.
     * @tparam T an integral integer type
     * @param x the integral integer
     * @param sign_is_digit if true and value is negative, adds one to result for sign. Defaults to true.
     * @return digit count
     */
    template<std::integral T>
    constexpr size_t digits10(const T x, const bool sign_is_digit = true) noexcept {
        return digits10<T>(x, jau::sign<T>(x), sign_is_digit);
    }
 
    /**
     * Returns the number of digits of the given unsigned integral value number and
     * the given radix.
     * @tparam T an integral unsigned integer type
     * @param x the integral integer
     * @param radix base of the number system, e.g. 2 binary, 8 octal, 10 decimal,
     * 16 hexadecimal, ..
     * @return digit count
     */
    template<jau::req::unsigned_integral T>
    constexpr size_t digits(const T x, const nsize_t radix) noexcept {
        if ( x == 0 ) {
            return 1;
        }
        switch ( radix ) {
            case 2:
                return 1 + static_cast<nsize_t>(std::log2<T>(x));
            case 10:
                return 1 + static_cast<nsize_t>(std::log10<T>(x));
            default:
                return 1 + static_cast<nsize_t>(std::log10<T>(x) / std::log10<T>(radix));
        }
    }
 
    /**@}*/
 
}  // namespace jau
 
#endif /* JAU_INT_MATH_HPP_ */