Funzione branchless int max/min templatizzata

Question

Sto provando a scrivere una funzione senza ramo per restituire il MAX o il MIN di due numeri interi senza ricorrere a if (o? :). Utilizzando the usual technique posso farlo abbastanza facilmente per una data dimensione parola:

inline int32 imax(int32 a, int32 b) 
{ 
    // signed for arithmetic shift 
    int32 mask = a - b; 
    // mask < 0 means MSB is 1. 
    return a + ((b - a) & (mask >> 31)); 
} 

Ora, supponendo arguendo che mi sto scrivendo il tipo di applicazione sul tipo di processore in-ordine dove ciò sia necessario, la mia domanda è se esiste un modo per utilizzare i modelli C++ per generalizzare questo a tutte le dimensioni di int.

Il passo >> 31 funziona solo per int32s, naturalmente, e mentre ho potuto copiare fuori sovraccarichi sulla funzione per int8, Int16, Int64 e, sembra che devo usare una funzione template, invece. Ma come ottengo la dimensione di un argomento modello in bit?

C'è un modo migliore per farlo rispetto a questo? Posso forzare la firma della maschera T? Se T non è firmato, il passaggio di spostamento della maschera non funzionerà (perché sarà uno spostamento logico piuttosto che aritmetico).

template< typename T > 
inline T imax(T a, T b) 
{ 
    // how can I force this T to be signed? 
    T mask = a - b; 
    // I hope the compiler turns the math below into an immediate constant! 
    mask = mask >> ((sizeof(T) * 8) - 1); 
    return a + ((b - a) & mask); 
} 

E, dopo aver fatto quanto sopra, posso impedire che venga utilizzato per qualsiasi cosa, ma un tipo intero (ad esempio, nessun galleggianti o classi)?

Answer 1

Generalmente, sembra buono, ma per la portabilità al 100%, sostituire quello 8 con CHAR_BIT (o numeric_limits :: max()) poiché non è garantito che i caratteri siano 8 bit.

Qualsiasi buon compilatore sarà abbastanza intelligente da unire tutte le costanti matematiche al momento della compilazione.

È possibile forzarlo per firmare utilizzando una libreria di caratteri di tipo. che di solito un aspetto simile (supponendo che il numeric_traits libreria si chiama numeric_traits):

typename numeric_traits<T>::signed_type x; 

Un esempio di un colpo di testa numeric_traits laminati manualmente potrebbe assomigliare a questo: http://rafb.net/p/Re7kq478.html (v'è abbondanza di spazio per le aggiunte, ma si ottiene la idea).

o, meglio ancora, l'uso spinta:

typename boost::make_signed<T>::type x; 

EDIT: IIRC, firmato sposta verso destra non devono essere aritmetica. È comune, e certamente il caso con ogni compilatore che ho usato. Ma credo che lo standard lasci il compilatore se i turni giusti sono aritmetici o meno sul tipo firmato. Nella mia copia del progetto di norma è scritto quanto segue:

Il valore di E1 >> E2 è E1 rightshifted posizioni E2 bit. Se E1 ha un tipo senza segno o E1 ha un tipo firmato e un valore negativo, il valore del risultato è la parte integrante del quoziente di E1 divisa per la quantità 2 elevato E2 potenza. Se E1 ha un tipo firmato e un valore negativo, il valore risultante è definito dall'implementazione.

Ma come ho detto, funzionerà su ogni compilatore che ho visto :-p.

Answer 2

Si consiglia di esaminare la libreria Boost.TypeTraits. Per rilevare se un tipo è firmato puoi utilizzare il tratto is_signed. È inoltre possibile esaminare enable_if/disable_if per rimuovere sovraccarichi per alcuni tipi.

Answer 3

Ecco un altro approccio per max e min senza ramo. La cosa bella è che non usa trucchetti e non devi sapere nulla del tipo.

template <typename T> 
inline T imax (T a, T b) 
{ 
    return (a > b) * a + (a <= b) * b; 
} 

template <typename T> 
inline T imin (T a, T b) 
{ 
    return (a > b) * b + (a <= b) * a; 
}