Qual è il miglior modo C++ per moltiplicare in modo modulare gli interi senza segno?

Question

Diciamo che si sta utilizzando <cstdint> e tipi come std::uint8_t e std::uint16_t, e vogliono fare operazioni come += e *= su di loro. Ti piacerebbe che l'aritmetica su questi numeri si articolasse in modo modulare, come tipico in C/C++. Questo di solito funziona, e si trova sperimentalmente funziona con std::uint8_t, std::uint32_t e std::uint64_t, ma non std::uint16_t.

In particolare, la moltiplicazione con std::uint16_t a volte fallisce in modo spettacolare, con build ottimizzati che producono tutti i tipi di risultati strani. La ragione? Comportamento indefinito a causa di overflow di interi con segno. Il compilatore si sta ottimizzando basandosi sul presupposto che il comportamento non definito non si verifichi, e quindi avvia pezzi di codice di eliminazione dal programma. Il comportamento non definito specifica è la seguente:

std::uint16_t x = UINT16_C(0xFFFF); 
x *= x; 

Il motivo è regole di promozione C++ s 'e il fatto che voi, come quasi tutti gli altri in questi giorni, si utilizza una piattaforma su cui std::numeric_limits<int>::digits == 31. Cioè, int è 32 bit (digits conta i bit ma non il bit di segno). x viene promosso a signed int, nonostante sia senza firma e 0xFFFF * 0xFFFF overflow per aritmetica con segno a 32 bit.

demo del problema generale:

// Compile on a recent version of clang and run it: 
// clang++ -std=c++11 -O3 -Wall -fsanitize=undefined stdint16.cpp -o stdint16 

#include <cinttypes> 
#include <cstdint> 
#include <cstdio> 

int main() 
{ 
    std::uint8_t a = UINT8_MAX; a *= a; // OK 
    std::uint16_t b = UINT16_MAX; b *= b; // undefined! 
    std::uint32_t c = UINT32_MAX; c *= c; // OK 
    std::uint64_t d = UINT64_MAX; d *= d; // OK 

    std::printf("%02" PRIX8 " %04" PRIX16 " %08" PRIX32 " %016" PRIX64 "\n", 
     a, b, c, d); 

    return 0; 
} 

si otterrà un bel errore:

main.cpp:11:55: runtime error: signed integer overflow: 65535 * 65535 
    cannot be represented in type 'int' 

Il modo per evitare questo, naturalmente, è quello di gettare almeno unsigned int prima di moltiplicare. Solo il caso esatto in cui il numero di bit del tipo unsigned corrisponde esattamente alla metà del numero di bit di int è problematico. Qualsiasi più piccolo comporterebbe la moltiplicazione non essendo in grado di traboccare, come con std::uint8_t; più grande risulterebbe nel tipo esattamente mappato a uno dei gradi di promozione, come con std::uint64_t corrispondente a unsigned long o unsigned long long a seconda della piattaforma.

Ma questo fa davvero schifo: richiede sapere quale tipo è problematico in base alle dimensioni di int sulla piattaforma corrente. C'è un modo migliore con il quale un comportamento indefinito con moltiplicazione di interi senza segno può essere evitato senza labirinti #if?

Answer 1

Questo articolo relativo a una soluzione C al caso di uint32_t * uint32_t moltiplicazione su un sistema in cui è int 64 bit ha una soluzione molto semplice che non avevo pensato: 32 bit unsigned multiply on 64 bit causing undefined behavior?

Tale soluzione, tradotto al mio problema, è semplice:

static_cast<std::uint16_t>(1U * x * x) 

di mera 1U nel lato sinistro della catena di operazioni aritmetiche li ke che promuoverà il primo parametro al più grande rango di unsigned int e std::uint16_t, quindi così via lungo la catena. La promozione assicurerà che la risposta sia non firmata e che i bit richiesti rimangano presenti. Il cast finale lo riduce di nuovo al tipo desiderato.

Questo è davvero semplice ed elegante, e vorrei averlo pensato un anno fa. Grazie a tutti coloro che hanno risposto prima.

Answer 2

Alcuni modelli con metaprogrammazione con SFINAE, forse.

#include <type_traits> 

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) <= sizeof(unsigned int)) , int>::type = 0> 
T safe_multiply(T a, T b) { 
    return (unsigned int)a * (unsigned int)b; 
} 

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) > sizeof(unsigned int)) , int>::type = 0> 
T safe_multiply(T a, T b) { 
    return a * b; 
} 

Demo.

Edit: più semplice:

template <typename T, typename std::enable_if<std::is_unsigned<T>::value, int>::type = 0> 
T safe_multiply(T a, T b) { 
    typedef typename std::make_unsigned<decltype(+a)>::type typ; 
    return (typ)a * (typ)b; 
} 

Demo.

Answer 3

Ecco una soluzione relativamente semplice, che costringe una promozione per unsigned int invece di int per tipo unsigned più stretta di un int. Non penso che nessun codice sia generato da promote, o almeno non più codice rispetto alla promozione di interi standard; importerà semplicemente la moltiplicazione ecc.utilizzare ops firmati invece di quelli firmati:

#include <type_traits> 
// Promote to unsigned if standard arithmetic promotion loses unsignedness 
template<typename integer> 
using promoted = 
    typename std::conditional<std::numeric_limits<decltype(integer() + 0)>::is_signed, 
          unsigned, 
          integer>::type; 

// function for template deduction 
template<typename integer> 
constexpr promoted<integer> promote(integer x) { return x; } 

// Quick test 
#include <cstdint> 
#include <iostream> 
#include <limits> 
int main() { 
    uint8_t i8 = std::numeric_limits<uint8_t>::max(); 
    uint16_t i16 = std::numeric_limits<uint16_t>::max(); 
    uint32_t i32 = std::numeric_limits<uint32_t>::max(); 
    uint64_t i64 = std::numeric_limits<uint64_t>::max(); 
    i8 *= promote(i8); 
    i16 *= promote(i16); 
    i32 *= promote(i32); 
    i64 *= promote(i64); 

    std::cout << " 8: " << static_cast<int>(i8) << std::endl 
      << "16: " << i16 << std::endl 
      << "32: " << i32 << std::endl 
      << "64: " << i64 << std::endl; 
    return 0; 
}