Templatized branchless int max/min función

Question

Estoy tratando de escribir una función sin sucursales para devolver el MAX o MIN de dos enteros sin recurrir a if (o? :). Usando the usual technique me puede hacer esto con bastante facilidad para un tamaño de palabra dada:

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)); 
} 

Ahora, suponiendo arguendo que realmente estoy escribiendo el tipo de aplicación en el tipo de procesador en el orden en que sea necesario, mi pregunta es si hay una forma de usar plantillas C++ para generalizar esto a todos los tamaños de int.

El paso >> 31 sólo funciona para int32s, por supuesto, y aunque podría copiar a cabo sobrecargas en la función para INT8, Int16, Int64 y, parece como si tuviera que utilizar una función de plantilla en su lugar. Pero, ¿cómo obtengo el tamaño de un argumento de plantilla en bits?

¿Hay una mejor manera de hacerlo que esta? ¿Puedo forzar la máscara T para que se firme? Si T no tiene firma, el paso de cambio de máscara no funcionará (porque será un cambio lógico en lugar de aritmético).

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); 
} 

Y, después de haber hecho lo anterior, puedo evitar que se utilice para otra cosa que un tipo entero (por ejemplo, no hay flotadores o clases)?

Answer 1

En general, se ve bien, pero para una portabilidad del 100%, reemplace ese 8 con CHAR_BIT (o numeric_limits :: max()) ya que no se garantiza que los caracteres sean de 8 bits.

Cualquier buen compilador será lo suficientemente inteligente como para fusionar todas las constantes matemáticas en tiempo de compilación.

Puede forzar que se firme utilizando una biblioteca de rasgos de tipo. que por lo general algo como (asumiendo que su numeric_traits biblioteca se llama numeric_traits):

typename numeric_traits<T>::signed_type x; 

Un ejemplo de una cabecera numeric_traits laminado manual podría tener este aspecto: http://rafb.net/p/Re7kq478.html (hay mucho espacio para las adiciones, pero se obtiene la idea).

o mejor aún, el uso de impulso:

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

EDIT: IIRC, firmaron desplazamientos a la derecha hacer no tiene por qué ser aritmética. Es común, y ciertamente el caso con cada compilador que he usado. Pero creo que el estándar deja al compilador si los cambios correctos son aritméticos o no en el tipo firmado. En mi copia del proyecto de norma se escribe lo siguiente:

El valor de E1 E2 es E1 >> rightshifted posiciones de bit E2. Si E1 tiene un tipo sin signo o si E1 tiene un tipo firmado y un valor no negativo, el valor del resultado es la parte entera del cociente de E1 dividido por la cantidad de 2 elevado a la E2 poder. Si E1 tiene un tipo con signo y un valor negativo, el valor resultante es la implementación definida.

Pero como he dicho, funcionará en cada compilador que he visto :-p.

Answer 2

Es posible que desee mirar la biblioteca Boost.TypeTraits. Para detectar si un tipo está firmado, puede usar el rasgo is_signed. También puede consultar enable_if/disable_if para eliminar sobrecargas para ciertos tipos.

Answer 3

Aquí hay otro enfoque para max y min sin sucursales. Lo bueno de esto es que no utiliza ningún truco de bits y no es necesario saber nada sobre el 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; 
}