Metafunzione per calcolare x^n e restituire il numero intero senza overflow se non possibile?

Question

Si consideri il seguente codice:

template <std::intmax_t Base, std::intmax_t Exponent> 
struct integer_power_bounded 
{ 
    static_assert(Exponent >= 0, 
        "Error in 'integer_power_bounded': 'Exponent >= 0' is false"); 
    static constexpr std::intmax_t value = /* something */; 
}; 

template <std::intmax_t Base> 
struct integer_power_bounded<Base, 0> 
{ 
    static constexpr std::intmax_t value = 1; 
}; 

Invece di /* something */, vorrei tornare std::numeric_limits<std::intmax_t>::min() o std::numeric_limits<std::intmax_t>::max() se Base^Exponent non può essere rappresentato da un std::intmax_t. La cosa difficile è evitare gli overflow durante il calcolo perché creano errori nella compilazione.

Come fare (senza boost)?

Answer 1

Una versione basata su SFINAE:

#include <cstdint> 
#include <cmath> 
#include <limits> 
#include <type_traits> 

constexpr std::intmax_t integer_power(std::intmax_t base, 
             std::intmax_t exponent) 
{ 
    return (exponent == 0) ? 1 : 
      (exponent % 2 == 0) ? integer_power(base, exponent/2) 
           *integer_power(base, exponent/2) : 
      base*integer_power(base, exponent-1); 
} 

namespace detail 
{ 
    template<std::intmax_t base, std::intmax_t exponent, 
      std::intmax_t res = integer_power(base,exponent)> 
    constexpr std::intmax_t pow_helper(int) 
    { 
     return res; 
    } 

    template<std::intmax_t base, std::intmax_t exponent> 
    constexpr std::intmax_t pow_helper(...) 
    { 
     return (exponent%2 == 0 || base > 0) 
       ? std::numeric_limits<std::intmax_t>::max() 
       : std::numeric_limits<std::intmax_t>::min(); 
    } 
} 

template<std::intmax_t base, std::intmax_t exponent> 
constexpr std::intmax_t integer_power_bounded() 
{ 
    return detail::pow_helper<base,exponent>(0); 
} 

Esempio di utilizzo:

#include <iostream> 
int main() 
{ 
    std::cout << sizeof(std::intmax_t) << '\n'; 

    constexpr auto p2t6 = integer_power_bounded<2, 6>(); 
    constexpr auto p2t62 = integer_power_bounded<2, 62>(); 
    constexpr auto p2t63 = integer_power_bounded<2, 63>(); 
    constexpr auto p2t64 = integer_power_bounded<2, 64>(); 
    constexpr auto p2t65 = integer_power_bounded<2, 65>(); 

    std::cout << "2^6 == " << p2t6 << '\n'; 
    std::cout << "2^62 == " << p2t62 << '\n'; 
    std::cout << "2^63 == " << p2t63 << '\n'; 
    std::cout << "2^64 == " << p2t64 << '\n'; 
    std::cout << "2^65 == " << p2t65 << '\n'; 

    constexpr auto pm2t6 = integer_power_bounded<-2, 6>(); 
    constexpr auto pm2t62 = integer_power_bounded<-2, 62>(); 
    constexpr auto pm2t63 = integer_power_bounded<-2, 63>(); 
    constexpr auto pm2t64 = integer_power_bounded<-2, 64>(); 
    constexpr auto pm2t65 = integer_power_bounded<-2, 65>(); 

    std::cout << "-2^6 == " << pm2t6 << '\n'; 
    std::cout << "-2^62 == " << pm2t62 << '\n'; 
    std::cout << "-2^63 == " << pm2t63 << '\n'; 
    std::cout << "-2^64 == " << pm2t64 << '\n'; 
    std::cout << "-2^65 == " << pm2t65 << '\n'; 
} 

uscita:

 
8 
2^6 == 64 
2^62 == 4611686018427387904 
2^63 == 9223372036854775807 
2^64 == 9223372036854775807 
2^65 == 9223372036854775807 
-2^6 == 64 
-2^62 == 4611686018427387904 
-2^63 == -9223372036854775808 
-2^64 == 9223372036854775807 
-2^65 == -9223372036854775808

---

Spiegazione:

012.

Un'espressione costante non può contenere un comportamento non definito [expr.const]/2:

• un'operazione che avrebbe comportamento indefinito [Nota: compresi, per esempio, troppopieno intero con segno, certo puntatori , divisione per zero o certe operazioni di cambio - nota finale];

Pertanto, ogni volta che il illimitatainteger_power produce un overflow, l'espressione utilizzata per dichiarare il std::integral_constant c'è un'espressione costante valida; la sostituzione fallisce e viene utilizzata la funzione fallback.