Me dijeron que (i >> 3) is faster than (i/8) pero no puedo encontrar ninguna información sobre qué >> es. ¿Alguien puede señalarme un enlace que lo explique?¿Qué significa >> y 0xfffffff8?
La misma persona me dijo "int k = i/8, seguido por k*8 se logra mejor mediante (i&0xfffffff8);" pero de nuevo Google no ayudó a m ...
Gracias por los enlaces!
Como se explica here el operador >> es simplemente un cambio de bit a bit de los bits de i.Por lo tanto, al desplazar i 1 bit a la derecha, se obtiene una división de números enteros por 2 y el desplazamiento por 3 bits da como resultado una división por 2^3 = 8.
Pero hoy en día esta optimización para la división por una potencia de dos ya no debería hacerse, ya que los compiladores deberían ser lo suficientemente inteligentes como para hacerlo ellos mismos.
mismo modo un AND bit a bit con 0xFFFFFFF8 (1 ... 1000, 3 últimos bits 0) es igual al redondeo hacia abajo i al múltiplo más cercano de 8 (como (i/8)*8 hace), ya que será cero los 3 últimos bits de i .
Proporcione un enlace para el OP: '¿Alguien puede indicarme un enlace que lo explique?' –
@JonathanM Hecho, buena razón para un voto negativo. Siempre aprecio las respuestas explicativas más que los enlaces a google o Wikipedia, pero probablemente tengas razón al decir que explícitamente me pidió un enlace. –
¡Gracias a todos por las respuestas! – Joel
Con respecto a la primera mitad:
>> es un cambio de bit a bit a la derecha.
Así desplazamiento de un valor numérico 3 bits a la derecha es lo mismo que dividir por 8 y int ing el resultado.
Aquí es una buena referencia para los operadores y su precedencia: http://web.cs.mun.ca/~michael/c/op.html
La segunda parte de su pregunta implica que el operador &, que es un AND de bits. El ejemplo es ANDing i y un número que deja todos los bits establecidos excepto los 3 menos significativos. Eso es esencialmente lo mismo que sucede cuando tienes un número, lo divide por 8, almacena el resultado como un entero, luego multiplica ese resultado por 8.
La razón por la que esto es así es porque se divide entre 8 y se almacena como entero es lo mismo que cambiar de bit a los 3 lugares correctos, y multiplicar por 8 y almacenar el resultado en un int es lo mismo que cambiar de bit a los 3 lugares a la izquierda.
Por lo tanto, si está multiplicando o dividiendo por una potencia de 2, como 8, y va a aceptar el truncamiento de bits que ocurre cuando almacena ese resultado en int, el cambio de bit es más rápido operacionalmente Esto se debe a que el procesador puede omitir el algoritmo de multiplicar/dividir y simplemente ir directamente a los bits de desplazamiento, lo que implica unos pocos pasos.
Bitwise shift right. i >> 3 mueve el número entero i 3 lugares a la derecha [vía binaria] - también conocido como, divide por 2^3.
>> es right shift operation.
Si tiene un número 8, que se representa en binario como 00001000, desplazar los bits a la derecha en 3 posiciones le dará 00000001, que es el decimal 1. Esto es equivalente a dividir por 2 tres veces.
La división y la multiplicación por el mismo número significa que usted establece algunos bits a la derecha en cero. Lo mismo se puede hacer si aplica una máscara. Digamos que 0xF8 es 11111000 bitwise y si lo ANDAS a un número, establecerá sus últimos tres bits a cero, y otros bits se dejarán como están. Por ejemplo, 10 & 0xF8 sería 00001010 & 11111000, que equivale a 00001000 u 8 en decimal.
Por supuesto, si utiliza variables de 32 bits, debe tener una máscara que se ajuste a este tamaño, por lo que tendrá todos los bits configurados en 1, excepto los tres bits de la derecha, que le dan su número - 0xFFffFFf8.
Ellos son Bitwise Operations
El operador >> es el operador de desplazamiento de bits. Toma el bit representado por el valor y lo desplaza en un número determinado de ranuras a la derecha.
Su desplazar los bits en binario así por ejemplo:
1000 == 8
0100 == 4 (>> 1)
0010 == 2 (>> 2)
0001 == 1 (>> 3)
Siendo que está utilizando un sistema base dos, puede aprovechar ciertos divisores (¡enteros solamente!) Y solo cambiar de bit. Además de eso, creo que la mayoría de los compiladores lo saben y lo harán por ti.
En cuanto a la segunda parte:
(i & 0xfffffff8);
decir que = 16
0x00000010 & 0xfffffff8 == 16
(16/8) * 8 == 16
Tomando de nuevo ventaja de operadores lógicos en binario. Investigue cómo los operadores lógicos trabajan en binario un poco más para una comprensión realmente clara de lo que está sucediendo a nivel de bit (y cómo leer hexadecimal).
Eso se llama desplazamiento de bits, que es una operación en trozos, por ejemplo, si usted tiene un número en una base binaria, digamos 8, será 1000, por lo que
x = 1000;
y = x >> 1; //y = 100 = 4
z = x >> 3; //z = 1
int x = i/8 * 8:
1) i/8, se puede reemplazar con i >> 3 - desplazamiento de bit a bit a la derecha en 3 dígitos (8 = 2^3)
2) i & xfffffff8 comparación con máscara Por ejemplo, tiene:
i = 11111111
k (i/8) would be: 00011111
x (k * 8) would be: 11111000
Por lo tanto la operación simplemente restablece 3 últimos bits: y comparables tiempo de multiplicación de costos y operación de división se pueden reescribir sencillas con
i & xfffffff8 - la comparación con (...11111000 máscara)
Cambio de bit a bit.
Supongamos que tengo un 8 bits número entero, en binario
Si desplazamiento a la izquierda (>> operador) 1 el resultado es
Si, a continuación, cambio a la derecha (< < operador) 1, que claramente vuelva a llevar empecé
Resulta que debido a que el primer entero binario es equivelant a
0 * 2^7 + 1 * 2^6 + 0 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0
o simplemente 2^6 o 64
Cuando desplazamiento a la derecha 1 obtenemos la siguiente
0 * 2^7 + 0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0
o simplemente 2^5 o 32
que significa
i >> 1
es la misma que
i/2
si cambiamos una vez más (i >> 2), que efectivamente divide por 2, una vez más y nos
i/2/2
que es realmente
i/4
No es una prueba matemática, pero se puede ver lo siguiente es verdadero
i >> n == i/(2^n)
>> desplaza el número a la derecha. Considere un número binario 0001000 que representa 8 en la notación decimal. Al desplazarlo 3 bits hacia la derecha, obtendría 0000001, que es el número 1 en notación decimal. Por lo tanto, puede ver que cada desplazamiento de 1 bit a la derecha es de hecho una división entre 2. Observe que el operador trunca la parte flotante del resultado. Por lo tanto i >> n implica i/2^n. Esto puede ser rápido dependiendo de la implementación del compilador. Pero generalmente tiene lugar justo en los registros y, por lo tanto, es muy rápido en comparación con la división tradicional y la multiplicación.
La respuesta a la segunda parte está contenida en la primera. Como la división también trunca toda la parte flotante del resultado, la división por 8 en teoría cambiará su número 3 bits a la derecha, perdiendo así toda la información sobre los 3 bits más a la derecha. Ahora cuando vuelves a multiplicarlo por 8 (que en teoría significa cambiar a la izquierda en 3 bits), estás rellenando los bits más cercanos 3 por cero después de cambiar el resultado dejado por 3 bits. Por lo tanto, la operación completa se puede considerar como una operación "&" con 0xfffffff8, lo que significa que el número tiene todos los bits 1 excepto los 4 bits más a la derecha que son 1000.
'i >> 3' es/solo puede ser más rápido que' i/8' en un compilador que es * absolutamente horrible * en las optimizaciones. No se preocupe, escriba el código más claro ;-) –
Quien le haya dicho eso probablemente todavía esté viviendo en los * días de gloria * del montaje de la escritura. Convertir cosas como 'i/8' a' i >> 3' se llama [reducción de la resistencia] (https://secure.wikimedia.org/wikipedia/en/wiki/Strength_reduction) y es una de las optimizaciones más básicas realizadas por compiladores. – Praetorian