¿Cuál es su técnica de bit-sabio favorita? [cerrado]

14

Hace unos días, el miembro de StackExchange Anto preguntó acerca de los usos válidos para operadores de bit bitwise. Declaré que desplazar era más rápido que multiplicar y dividir enteros por potencias de dos. El miembro de StackExchange, Daemin, respondió diciendo que el desplazamiento a la derecha presentaba problemas con números negativos.

En ese momento, nunca había pensado realmente en usar los operadores de cambio con enteros con signo. Principalmente utilicé esta técnica en el desarrollo de software de bajo nivel; por lo tanto, siempre he usado enteros sin signo. C realiza desplazamientos lógicos en enteros sin signo. No se presta atención al bit de signo cuando se realiza un cambio lógico a la derecha. Los bits desocupados se rellenan con ceros. Sin embargo, C realiza una operación de cambio aritmético cuando se desplaza un entero con signo a la derecha. Los bits vacantes se rellenan con el bit de signo. Esta diferencia hace que un valor negativo se redondee hacia el infinito en lugar de truncarlo hacia cero, lo que es un comportamiento diferente al de la división de enteros con signo.

Unos pocos minutos de reflexión dieron como resultado una solución de primer orden. La solución convierte condicionalmente los valores negativos en valores positivos antes de cambiar. Un valor se convierte condicionalmente de nuevo a su forma negativa después de que se haya realizado la operación de cambio.

int a = -5;
int n = 1;

int negative = q < 0; 

a = negative ? -a : a; 
a >>= n; 
a = negative ? -a : a; 

El problema con esta solución es que las instrucciones de asignación condicional generalmente se traducen a al menos una instrucción de salto, y las instrucciones de salto pueden ser costosas en los procesadores que no descodifican ambas rutas de instrucciones. Tener que volver a preparar una tubería de instrucciones dos veces hace una buena mella en cualquier ganancia de rendimiento obtenida al cambiar la división.

Con lo dicho anteriormente, me desperté el sábado con la respuesta al problema de asignación condicional. El problema de redondeo que experimentamos al realizar una operación de cambio aritmético solo ocurre cuando se trabaja con la representación de complemento de dos. No ocurre con la representación del complemento de uno. La solución al problema consiste en convertir el valor de complemento de dos en un valor de complemento de uno antes de realizar la operación de cambio. Luego tenemos que convertir el valor de complemento de uno de nuevo en un valor de complemento de dos. Sorprendentemente, podemos realizar este conjunto de operaciones sin convertir condicionalmente los valores negativos antes de realizar la operación de cambio.

int a = -5;
int n = 1;

register int sign = (a >> INT_SIZE_MINUS_1) & 1

a = (a - sign) >> n + sign;   

El valor negativo del complemento a dos se convierte al valor negativo del complemento a uno restando uno. Por otro lado, el valor negativo del complemento de uno se convierte en el valor negativo del complemento de dos agregando uno. El código enumerado anteriormente funciona porque el bit de signo se utiliza para convertir el complemento de dos al complemento de uno y y viceversa . Sólo los valores negativos tendrán sus bits de signo establecidos; por lo tanto, la variable sign será igual a cero cuando a sea positivo.

Con lo dicho anteriormente, ¿puedes pensar en otros hacks de sabio de bits como el anterior que han llegado a tu bolsa de trucos? ¿Cuál es tu truco favorito? Siempre estoy buscando nuevos hacks en cuanto a rendimiento orientados a bits.

    
pregunta bit-twiddler 11.04.2011 - 05:52
fuente

0 respuestas

Lea otras preguntas en las etiquetas