math - tablas - rotacion de bits en c

¿Los operadores bitwise(aparte de los turnos) tienen algún sentido matemático en la base 10?

Question

Según wiki se pueden usar turnos para calcular potencias de 2:

Un cambio aritmético izquierdo por n es equivalente a multiplicar por 2 ^ n (siempre que el valor no se desborde), mientras que un cambio aritmético derecho por n del valor de complemento de dos es equivalente a dividir por 2 ^ n y redondear hacia el infinito negativo.

Siempre me preguntaba si algún otro operador bitwise ( ~ , | , & , ^ ) tiene algún sentido matemático cuando se aplica a base-10. Entiendo cómo funcionan, pero ¿se pueden usar los resultados de tales operaciones para calcular algo útil en el mundo decimal?

Answer 1

En algún momento puede sustituir operaciones bitwise por operaciones booleanas. Por ejemplo, el siguiente código:

if ((a < 0) && (b < 0) { do something {

En C esto puede ser reemplazado por:

if ((a & b) < 0) { do something {

Esto funciona porque se usa un bit en un entero como el bit de signo (1 indica negativo). La operación y (a y b) será un número sin sentido, pero su signo será a nivel de bits y de los signos de los números y, por lo tanto, la verificación del signo del resultado funcionará.

Esto puede o no beneficiar el rendimiento. Hacer dos pruebas booleanas / ramas será peor en varias arquitecturas y compiladores. Los compiladores x86 modernos probablemente pueden generar una sola rama usando algunas de las instrucciones más nuevas incluso con la sintaxis normal.

Como siempre, si resulta en un aumento de rendimiento ... Comente el código, es decir, ponga la forma "normal" de hacerlo en un comentario y diga que es equivalente pero más rápido.

Del mismo modo, ~ | y ^ se puede usar de manera similar si todas las condiciones son (x <0). Para condiciones de comparación, generalmente puedes usar la resta:

if ((a < b) | (b < c)) { }

se convierte en:

if (((a-b) | (b-c)) < 0) { }

porque ab será negativo solo si a es menor que b. Puede haber problemas con este si obtiene dentro de un factor de 2 de max int, es decir, desbordamiento aritmético, así que tenga cuidado.

Estas son optimizaciones válidas en algunos casos, pero por lo demás bastante inútiles. Y para ser realmente feos, los números de punto flotante también tienen bits de signo ... ;-)

EJEMPLO: como ejemplo, supongamos que desea realizar una acción en función del orden de a, b, c. Puedes hacer algunos anidados si / else construye, o puedes hacer esto:

x = ((a < b) << 2) | ((b < c) << 1) | (c < a); switch (x):

He usado esto en código con hasta 9 condiciones y también utilizando las restas mencionadas anteriormente con lógica adicional para aislar los bits de signo en lugar de menos de. Es más rápido que el equivalente de ramificación. Sin embargo, ya no es necesario realizar la extracción de la resta y el signo de extracción, ya que el estándar se actualizó hace mucho tiempo para especificar verdadero como 1, y con movimientos condicionales y demás, el real menor que puede ser bastante eficiente en estos días.

Answer 2

En todos los idiomas que he usado (es cierto, casi exclusivamente derivados de C y C), los operadores a nivel de bits son exclusivamente operaciones de enteros (a menos que, por supuesto, anulen la operación).

Si bien puedes dividir los bits de un número decimal (después de todo, tienen sus propios bits), no necesariamente te dará el mismo resultado que los bits de un número entero. Consulte Precisión única y Precisión doble para obtener descripciones de los bits en números decimales. Consulte Raíz cuadrada inversa rápida para ver un ejemplo del uso ventajoso de los números decimales de twiddling de bits.

EDITAR

Para los números integrales, las operaciones bitwise siempre tienen sentido. Las operaciones bitwise están diseñadas para los números integrales.

n << 1 == n * 2
n << 2 == n * 4
n << 3 == n * 8
n >> 1 == n / 2
n >> 2 == n / 4
n >> 3 == n / 8
n & 1 == {0, 1} // Set containing 0 and 1
n & 2 == {0, 2} // Set containing 0 and 2
n & 3 == {0, 1, 2, 3} // Set containing 0, 1, 2, and 3
n | 1 == {1, n, n+1}
n | 2 == {2, n, n+2}
n | 3 == {3, n, n+1, n+2, n+3}

Y así.

Answer 3

Puedes calcular logaritmos usando solo operadores bitwise ...

Encontrar el exponente de n = 2 ** x usando operaciones bitwise [logaritmo en la base 2 de n]

Answer 4

Sí, hay otras operaciones útiles, pero tienden a estar orientadas a operaciones que involucran potencias de 2 (por razones obvias), por ejemplo, prueba para impar / par, prueba de potencia de 2, redondeo hacia arriba / abajo a la potencia más cercana de 2, etc. .

Ver Hacker''s Delight por Henry S. Warren.

Answer 5

Un truco divertido para intercambiar dos enteros sin un temporal usando XOR a nivel de bits:

void swap(int &a, int &b) {
a = a ^ b;
b = b ^ a; //b now = a
a = a ^ b; //knocks out the original a
}

Esto funciona porque XOR es un conmutativo por lo que a ^ b ^ b = a.

Answer 6

"yep base-10 is what I mean"

En ese caso, sí, pueden extenderse a base-10 de varias maneras, aunque no son tan útiles como en binario.

Una idea es que & , | , etc. son lo mismo que hacer aritmética mod-2 a los dígitos binarios individuales. Si a y b son dígitos binarios únicos, entonces

a & b = a * b (mod 2) a ^ b = a + b (mod 2) ~a = 1-a (mod 2) a | b = ~(~a & ~b) = 1 - (1-a)*(1-b) (mod 2)

Los equivalentes en base 10 serían (tenga en cuenta que estos se aplican por dígito, no al número entero)

a & b = a * b (mod 10) a ^ b = a + b (mod 10) ~a = 9-a (mod 10) a | b = ~(~a & ~b) = 9 - (9-a)*(9-b) (mod 10)

Los primeros tres son útiles cuando se diseñan circuitos que usan BCD ( ~a es el complemento de los 9 ), como las calculadoras no gráficas, aunque solo usamos * y + lugar de & y ^ cuando escribimos las ecuaciones. El primero también se usa aparentemente en algunos cifrados antiguos .