c++ - paso - ¿Cuál es la mejor opción a usar para dividir un número entero por 2?

divisiones con decimales en dividendo y divisor ejercicios resueltos (23)

¿Cuál es la mejor opción y por qué para dividir el número entero por 2?

Depende de lo que quieras decir con mejor .

Si quiere que sus colegas lo odien o haga que su código sea difícil de leer, definitivamente me quedaría con la primera opción.

Si quieres dividir un número entre 2, ve con el segundo.

Los dos no son equivalentes, no se comportan igual si el número es negativo o dentro de expresiones más grandes: el cambio de bits tiene una precedencia más baja que + o - , la división tiene una precedencia más alta.

Debes escribir tu código para expresar cuál es su intención. Si le preocupa el rendimiento, no se preocupe, el optimizador hace un buen trabajo en este tipo de microoptimizaciones.

¿Cuál de las siguientes técnicas es la mejor opción para dividir un número entero por 2 y por qué?

Técnica 1:

x = x >> 1;

Técnica 2:

x = x / 2;

Aquí x es un número entero.

¿El primero parece dividirse? No. Si quieres dividir, usa x / 2 . El compilador puede optimizarlo para usar el cambio de bits si es posible (se llama reducción de la fuerza), lo que lo convierte en una microoptimización inútil si lo haces por tu cuenta.

Echa un vistazo a la salida del compilador para ayudarte a decidir. Corrí esta prueba en x86-64 con
gcc (GCC) 4.2.1 20070719 [FreeBSD]

También vea las salidas del compilador en línea en godbolt .

Lo que ves es que el compilador usa una instrucción sarl (desplazamiento aritmético a la derecha) en ambos casos, por lo que reconoce la similitud entre las dos expresiones. Si usa la división, el compilador también necesita ajustar los números negativos. Para hacer eso, desplaza el bit de signo hacia abajo al bit de orden más bajo, y lo agrega al resultado. Esto soluciona el problema de off-by-one al cambiar los números negativos, en comparación con lo que haría una división.
Como el caso de división hace 2 turnos, mientras que el caso de cambio explícito solo hace uno, ahora podemos explicar algunas de las diferencias de rendimiento medidas por otras respuestas aquí.

Código C con salida de montaje:

Para dividir, su entrada sería

int div2signed(int a) { return a / 2; }

y esto compila a

movl %edi, %eax shrl $31, %eax addl %edi, %eax sarl %eax ret

de manera similar para el turno

int shr2signed(int a) { return a >> 1; }

con salida:

sarl %edi movl %edi, %eax ret

En general el turno derecho divide:

q = i >> n; is the same as: q = i / 2**n;

esto se usa a veces para acelerar los programas a costa de la claridad. No creo que debas hacerlo. El compilador es lo suficientemente inteligente como para realizar la aceleración automáticamente. Esto significa que poner un turno no le gana nada a costa de la claridad .

Eche un vistazo a esta página de Practical C ++ Programming.

En lo que respecta a la CPU, las operaciones de cambio de bits son más rápidas que las operaciones de división. Sin embargo, el compilador lo sabe y se optimizará adecuadamente en la medida de lo posible, por lo que puede codificar de la manera que le resulte más sensata y fácil saber que su código se está ejecutando de manera eficiente. Pero recuerde que un unsigned int se puede optimizar (en algunos casos) mejor que un int por las razones señaladas anteriormente. Si no necesita aritmética con signo, no incluya el bit de signo.

En términos de rendimiento. Las operaciones de cambio de CPU son significativamente más rápidas que dividir los códigos de operación. Entonces, dividir por dos o multiplicar por 2, etc., todos se benefician de las operaciones de turno.

En cuanto a la apariencia. Como ingenieros, ¿cuándo nos volvimos tan apegados a los cosméticos que incluso las bellas damas no usan? :)

Estoy de acuerdo con otras respuestas en que debería favorecer x / 2 porque su intención es más clara, y el compilador debería optimizarlo para usted.

Sin embargo, otra razón para preferir x / 2 sobre x >> 1 es que el comportamiento de >> depende de la implementación si x es un int firmado y es negativo.

De la sección 6.5.7, punto 5 de la norma ISO C99:

El resultado de E1 >> E2 es E1 posiciones de bit E2 desplazadas a la derecha. Si E1 tiene un tipo sin signo o si E1 tiene un tipo con signo y un valor no negativo, el valor del resultado es la parte integral del cociente de E1 / 2 ^E2 . Si E1 tiene un tipo firmado y un valor negativo, el valor resultante se define por la implementación.

Haga que sus intenciones sean más claras ... por ejemplo, si desea dividir, use x / 2, y permita que el compilador lo optimice para cambiar de operador (o cualquier otra cosa).

Los procesadores de hoy no permitirán que estas optimizaciones tengan ningún impacto en el rendimiento de sus programas.

Knuth dijo:

La optimización prematura es la fuente de todos los males.

Así que sugiero usar x /= 2;

De esta manera, el código es fácil de entender y también creo que la optimización de esta operación en esa forma, no significa una gran diferencia para el procesador.

La respuesta a esto dependerá del entorno en el que estés trabajando.

Si está trabajando en un microcontrolador de 8 bits o cualquier cosa sin soporte de hardware para la multiplicación, el cambio de bits es normal y se espera que el compilador convierta x /= 2 en x >>= 1 , la presencia de una división El símbolo provocará más cejas en ese entorno que el uso de un cambio para efectuar una división.
Si está trabajando en un entorno de rendimiento crítico o una sección de código, o su código podría compilarse con la optimización del compilador desactivada, x >>= 1 con un comentario que explique su razonamiento es probablemente el mejor solo para claridad de propósito.
Si no está bajo una de las condiciones anteriores, haga que su código sea más legible simplemente usando x /= 2 . Es mejor guardar el siguiente programador que vea su código en la segunda toma doble de 10 segundos en su operación de turno que demostrar innecesariamente que sabía que el cambio era más eficiente que la optimización del compilador.

Todos estos asumen números enteros sin signo. El cambio simple probablemente no es lo que quieres para ser firmado. Además, DanielH presenta un buen punto sobre el uso de x *= 0.5 para ciertos lenguajes como ActionScript.

Lo digo con el propósito de programar competiciones. Generalmente tienen entradas muy grandes donde la división por 2 ocurre muchas veces y se sabe que la entrada es positiva o negativa.

x >> 1 será mejor que x / 2. Revisé ideone.com ejecutando un programa donde se realizaron más de 10 ^ 10 divisiones por 2 operaciones. x / 2 tomó casi 5.5 s, mientras que x >> 1 tomó casi 2.6 s para el mismo programa.

Mientras que x >> 1 es más rápido que x / 2, el uso adecuado de >> cuando se trata de valores negativos es un poco más complicado. Requiere algo similar a lo siguiente:

// Extension Method public static class Global { public static int ShiftDivBy2(this int x) { return (x < 0 ? x + 1 : x) >> 1; } }

Obviamente, si estás escribiendo tu código para el siguiente chico que lo lea, ve por la claridad de "x / 2".

Sin embargo, si la velocidad es su objetivo, inténtelo de manera simultánea y el tiempo de los resultados. Hace unos meses trabajé en una rutina de convolución de mapa de bits que incluía pasar por una matriz de enteros y dividir cada elemento por 2. Hice todo tipo de cosas para optimizarlo, incluido el viejo truco de sustituir "x >> 1" por "x / 2 ".

Cuando realmente cronometré en ambas direcciones, descubrí para mi sorpresa que x / 2 era más rápido que x >> 1

Esto estaba usando Microsoft VS2008 C ++ con las optimizaciones predeterminadas activadas.

Para apilar: hay muchas razones para favorecer el uso de x = x / 2; Aquí están algunas:

expresa tu intención más claramente (asumiendo que no estás tratando con bits de registro de twiddling de bits o algo así)
el compilador reducirá esto a una operación de cambio de todos modos
incluso si el compilador no lo redujo y eligió una operación más lenta que el turno, la probabilidad de que esto termine afectando el rendimiento de su programa de una manera mensurable es muy pequeña (y si lo afecta de manera mensurable, entonces tiene una razón para usar un turno)
Si la división va a ser parte de una expresión más grande, es más probable que obtenga la prioridad correcta si usa el operador de división:
x = x / 2 + 5; x = x >> 1 + 5; // not the same as above
la aritmética firmada podría complicar las cosas incluso más que el problema de precedencia mencionado anteriormente
Para reiterar: el compilador ya hará esto por usted de todos modos. De hecho, convertirá la división por una constante en una serie de turnos, sumas y multiplicaciones para todo tipo de números, no solo potencias de dos. Vea esta pregunta para ver enlaces a más información sobre esto.

En resumen, no compras nada codificando un turno cuando realmente quieres multiplicar o dividir, excepto tal vez una mayor posibilidad de introducir un error. Ha sido toda una vida desde que los compiladores no eran lo suficientemente inteligentes como para optimizar este tipo de cosas a un cambio cuando fuera apropiado.

Simplemente use divide ( / ), suponiendo que es más claro. El compilador se optimizará en consecuencia.

Solo una nota agregada -

x * = 0.5 a menudo será más rápido en algunos lenguajes basados en máquinas virtuales, especialmente ActionScript, ya que la variable no tendrá que verificarse para dividir entre 0.

Utilice x = x / 2; O x /= 2; Porque es posible que un nuevo programador trabaje en él en el futuro. Por lo tanto, le será más fácil descubrir qué está sucediendo en la línea de código. Todo el mundo puede no ser consciente de tales optimizaciones.

Utilice la operación que mejor describe lo que está tratando de hacer.

Si está tratando el número como una secuencia de bits, use bitshift.
Si lo estás tratando como un valor numérico, usa la división.

Tenga en cuenta que no son exactamente equivalentes. Pueden dar diferentes resultados para enteros negativos. Por ejemplo:

-5 / 2 = -2 -5 >> 1 = -3

(ideone)

X / Y es correcto ... y ">>" operador de cambio ... si queremos dividir un entero, podemos usar (/) operador de dividendo. operador de cambio se utiliza para desplazar los bits ..

x = x / 2; x / = 2; Podemos usar así ...

Yo diría que hay varias cosas a considerar.

Bitshift debería ser más rápido, ya que realmente no se necesita un cálculo especial para cambiar los bits, sin embargo, como se señaló, hay problemas potenciales con los números negativos. Si está seguro de tener números positivos, y está buscando velocidad, le recomendaría Bitshift.
El operador de división es muy fácil de leer para los humanos. Entonces, si está buscando la legibilidad del código, puede usar esto. Tenga en cuenta que el campo de la optimización del compilador ha recorrido un largo camino, por lo que hacer que el código sea fácil de leer y entender es una buena práctica.
Dependiendo del hardware subyacente, las operaciones pueden tener diferentes velocidades. La ley de Amdal es hacer rápido el caso común. Por lo tanto, es posible que tenga hardware que pueda realizar diferentes operaciones más rápido que otros. Por ejemplo, multiplicar por 0.5 puede ser más rápido que dividir por 2. (Concedido, es posible que tenga que tomar el piso de la multiplicación si desea imponer una división entera).

Si lo que busca es rendimiento puro, recomendaría crear algunas pruebas que podrían hacer las operaciones millones de veces. Pruebe la ejecución varias veces (su tamaño de muestra) para determinar cuál es mejor estadísticamente con su sistema operativo / hardware / compilador / código.

mod 2, prueba para = 1. dunno la sintaxis en c. pero esto puede ser más rápido.

x = x / 2; es el código adecuado para usar ... pero una operación depende de su propio programa de cómo producir la salida que desea producir.

x / 2 es más claro, y x >> 1 no es mucho más rápido (según un micro-benchmark, aproximadamente un 30% más rápido para una JVM de Java). Como han señalado otros, para los números negativos, el redondeo es ligeramente diferente, por lo que debe considerar esto cuando desee procesar números negativos. Algunos compiladores pueden convertir automáticamente x / 2 a x >> 1 si saben que el número no puede ser negativo (incluso pensé que no podía verificar esto).

Incluso x / 2 puede no usar la instrucción de CPU de división (lenta), porque algunos accesos directos son posibles , pero aún es más lento que x >> 1 .

(Esta es una pregunta de C / C ++, otros lenguajes de programación tienen más operadores. Para Java también existe el desplazamiento a la derecha sin signo, x >>> 1 , que también es diferente. Permite calcular correctamente el valor medio (promedio) de dos valores, de modo que (a + b) >>> 1 devolverá el valor medio incluso para valores muy grandes de a y b . Esto es necesario, por ejemplo, para la búsqueda binaria si los índices de la matriz pueden ser muy grandes. Hubo un error en muchas versiones de búsqueda binaria , porque utilizaron (a + b) / 2 para calcular el promedio. Esto no funciona correctamente. La solución correcta es usar (a + b) >>> 1 lugar.)