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

Hace unos días, el miembro de StackExchange Anto preguntó acerca de los usos válidos para los operadores de bit-wise. Dije que cambiar 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 usé enteros sin signo. C realiza cambios 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 vaciados se rellenan con ceros. Sin embargo, C realiza una operación de desplazamiento aritmético cuando desplaza un entero con signo a la derecha. Los bits desocupados se llenan con el bit de signo. Esta diferencia hace que un valor negativo se redondee hacia el infinito en lugar de truncarse hacia cero, que es un comportamiento diferente al de la división entera 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 en al menos una instrucción de salto, y las instrucciones de salto pueden ser costosas en procesadores que no decodifican ambas rutas de instrucciones. Tener que volver a cebar una tubería de instrucciones dos veces hace una buena mella en cualquier ganancia de rendimiento obtenida al cambiar sobre la división.

Dicho lo anterior, 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 trabajamos con la representación del complemento a dos. No ocurre con la representación del complemento de uno. La solución al problema consiste en convertir el valor del complemento de dos en el valor del complemento de uno antes de realizar la operación de cambio. Luego tenemos que convertir el valor del complemento de uno nuevamente al valor del 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 de dos se convierte en el valor negativo del complemento de uno restando uno. Por otro lado, el valor negativo del complemento de uno se convierte en el valor negativo del complemento de dos al sumar uno. El código mencionado anteriormente funciona porque el bit de signo se usa para convertir del complemento de dos al complemento de uno y viceversa . Solo los valores negativos tendrán sus bits de signo establecidos; por lo tanto, el signo variable será igual a cero cuando a es positivo.

Dicho lo anterior, ¿puedes pensar en otros trucos sabios como el anterior que se han convertido en tu bolsa de trucos? ¿Cuál es tu truco favorito de bit-wise? Siempre estoy buscando nuevos trucos orientados al rendimiento basados ​​en bits.

Me encanta el truco de Gosper (HAKMEM # 175), una forma muy astuta de tomar un número y obtener el siguiente número con el mismo número de bits establecido. Es útil, por ejemplo, para generar combinaciones de kelementos de esta nmanera:

int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    doStuff(set);

    // Gosper's hack:
    int c = set & -set;
    int r = set + c;
    set = (((r^set) >>> 2) / c) | r;
}

El método de raíz cuadrada inversa rápida utiliza las técnicas de nivel de bits más extrañas para calcular la inversa de una raíz cuadrada que he visto:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

División por 3: sin recurrir a una llamada a la biblioteca en tiempo de ejecución.

Resulta que la división por 3 (gracias a una pista sobre el desbordamiento de pila) se puede aproximar como:

X / 3 = [(x / 4) + (x / 12)]

Y X / 12 es (x / 4) / 3. Hay un elemento de recursión que aparece repentinamente aquí.

También resulta que si limita el rango de los números en los que está jugando, puede limitar el número de iteraciones necesarias.

Y por lo tanto, para enteros sin signo <2000, el siguiente es un algoritmo rápido y simple / 3. (Para números más grandes, solo agregue más pasos). Los compiladores optimizan el heck de esto para que sea rápido y pequeño:

FastDivide3 estático sin signo corto (const arg corto sin signo)
{
  unsigned short RunningSum;
  unsigned short fracctionthwelth;

  RunningSum = arg >> 2;

  FractionalTwelth = RunningSum >> 2;
  RunningSum + = FractionalTwelth;

  Fraccional Doce >> = 2;
  RunningSum + = FractionalTwelth;

  Fraccional Doce >> = 2;
  RunningSum + = FractionalTwelth;

  Fraccional Doce >> = 2;
  RunningSum + = FractionalTwelth;

  // Más repeticiones de las 2 líneas anteriores para mayor precisión.

  volver RunningSum;
}

Si miras en Erlang, hay un DSL completo para realizar operaciones de bit. Entonces, puede dividir una estructura de datos por bits diciendo algo como esto:

<> = << 1,17,42: 16 >>.

Detalles completos aquí: http://www.erlang.org/doc/reference_manual/expressions.html#id75782