¿Hay alguna forma de limitar un valor entero a un cierto rango sin ramificar?

Question

Solo por curiosidad. Si tengo algo como:

if(x < 0) 
    x = 0; 
if(x > some_maximum) 
    x = some_maximum; 

return x; 

¿Hay alguna manera de no ramificar? Esto es C++

Adición: Quiero decir que no hay instrucciones de bifurcación en el ensamblaje. Es una arquitectura MIPS.

Answer 1

Hay bits trucos para encontrar el mínimo o máximo de dos números, por lo que podría utilizar para encontrar los min(max(x, 0), some_maximum). De here:

y^((x^y) & -(x < y)); // min(x, y) 
x^((x^y) & -(x < y)); // max(x, y) 

Como los estados de origen sin embargo, es probablemente más rápido que hacerlo de la forma normal, a pesar de la rama

Answer 2

Depende de su arquitectura. Para ARM, al menos, el compilador probablemente emitiría instrucciones condicionalmente ejecutadas y el código máquina resultante no contendría una bifurcación. Sin embargo, no puedo pensar en una buena manera de hacerlo explícito en el programa C.

Answer 3

Usando el operador ternario :)

return x < 0 ? 0 : x > some_maximum ? : some_maximum : x; 

Answer 4

x = min(max(x,0),100); 

La ramificación está escondido muy bien dentro de las funciones con nombres normales.

Sugerencia para crear una plantilla clip_by.

Answer 5

Esto dependerá del compilador y del procesador, pero si usa ?:, se puede traducir a un movimiento condicional (al menos en procesadores basados ​​en Intel) que no utiliza una bifurcación.

x = x < 0 ? 0 : x; x = x > max ? max : x;

Esto puede utilizar la instrucción CMOV (ver http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc35.htm), cuyo propósito es evitar la ramificación (y sanciones de predicción por lo tanto Branch).

Editar: este thread puede ser de su interés. Los puntos de referencia muestran que los movimientos condicionales te darán ganancias de velocidad solo en ramas que no son muy predecibles, mientras que las ramas altamente predecibles (como la de un bucle de larga duración) prefieren el enfoque estándar.

Answer 6

x = ((int)(x > some_maximum)) * some_maximum 
    + ((int)(x > 0 && x <= some_maximum)) * x; 

Answer 7

Si es posible limitar a potencias de 2 (no incluido), a continuación, sólo tiene que ir con

int newx = x & ((highest power of 2) - 1)

no muy seguro para manejar el (si x < 0 caso) o la genérica (x < n caso)

Answer 8

Para problemas futuros como este, la página bit hack puede ser útil: http://graphics.stanford.edu/~seander/bithacks.html.

Desde el bithack de mínimo y máximo ya fue publicada, aquí es diferente:

// CHAR_BIT is number of bits per byte. 
// sign = 1 if x < 0, sign = 0 otherwise (according to the page above) 
int sign = (int)((unsigned int)((int)x) >> (sizeof(int) * CHAR_BIT - 1)); 

int y = (1-sign)*x; // if x < 0, then y = 0, else y = x. 

// Depending on arch, the below _might_ cause a branch. 
// (on x64 it does not cause a branch, not sure about MIPS) 

int z = !(y/some_maximum); // if 0 <= y < some_maximum, z = 1, else z = 0 

int ret = z*y + (1-z)*some_maximum; // if z =1, then ret = y; else ret = some_maximum. 

return ret; 

yo sólo probé y funcionó para los pocos casos de prueba que tenía.

Aquí está el código de ensamblaje de mi computadora (intel arch) que no muestra ramas.

int cap(int x) 
{ 
00F013A0 push  ebp 
00F013A1 mov   ebp,esp 
00F013A3 sub   esp,0FCh 
00F013A9 push  ebx 
00F013AA push  esi 
00F013AB push  edi 
00F013AC lea   edi,[ebp-0FCh] 
00F013B2 mov   ecx,3Fh 
00F013B7 mov   eax,0CCCCCCCCh 
00F013BC rep stos dword ptr es:[edi] 

    int some_maximum = 100; 

00F013BE mov   dword ptr [some_maximum],64h 

    // CHAR_BIT is number of bits per byte. 
    // sign = 1 if x < 0, sign = 0 otherwise (according to the page above) 
    int sign = (int)((unsigned int)((int)x) >> (sizeof(int) * CHAR_BIT - 1)); 

00F013C5 mov   eax,dword ptr [x] 
00F013C8 shr   eax,1Fh 
00F013CB mov   dword ptr [sign],eax 

    int y = (1-sign)*x; // if x < 0, then y = 0, else y = x. 

00F013CE mov   eax,1 
00F013D3 sub   eax,dword ptr [sign] 
00F013D6 imul  eax,dword ptr [x] 
00F013DA mov   dword ptr [y],eax 

    // Depending on arch, the below _might_ cause a branch. 
    // (on x64 it does not cause a branch, not sure about MIPS) 

    int z = !(y/some_maximum); // if 0 <= y < some_maximum, z = 1, else z = 0 

00F013DD mov   eax,dword ptr [y] 
00F013E0 cdq    
00F013E1 idiv  eax,dword ptr [some_maximum] 
00F013E4 neg   eax 
00F013E6 sbb   eax,eax 
00F013E8 add   eax,1 
00F013EB mov   dword ptr [z],eax 

    int ret = z*y + (1-z)*some_maximum; // if z =1, then ret = y; else ret = some_maximum. 

00F013EE mov   eax,dword ptr [z] 
00F013F1 imul  eax,dword ptr [y] 
00F013F5 mov   ecx,1 
00F013FA sub   ecx,dword ptr [z] 
00F013FD imul  ecx,dword ptr [some_maximum] 
00F01401 add   eax,ecx 
00F01403 mov   dword ptr [ret],eax 

    return ret; 

00F01406 mov   eax,dword ptr [ret] 
} 
00F01409 pop   edi 
00F0140A pop   esi 
00F0140B pop   ebx 
00F0140C mov   esp,ebp 
00F0140E pop   ebp 
00F0140F ret