¿Cuál es la mejor opción para dividir un número entero por 2?

¿El primero parece dividir? No. Si desea dividir, utilice x / 2. El compilador puede optimizarlo para usar bit-shift si es posible (se llama reducción de fuerza), lo que lo convierte en una microoptimización inútil si lo haces por tu cuenta.

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

• Expresa su intención más claramente (asumiendo que no está tratando con bits de registro de giro de bits o algo)

• 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 medible es en sí misma desvaneciéndose pequeño (y si lo afecta mensurablemente, entonces usted tiene una razón real para usar un cambio)

• Si la división va a ser parte de una expresión más grande, es más probable que obtenga la precedencia 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 aún más que el problema de precedencia mencionado anteriormente

• Para reiterar-el compilador ya hará esto por usted de todos modos. De hecho, se convertirá división por una constante a una serie de cambios, suma y multiplica para todo tipo de números, no solo potencias de dos. Ver esta pregunta para enlaces a más información sobre esto.

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

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

Depende de lo que quieres decir con mejor.

Si quieres que tus colegas te odien, o que tu código sea difícil de leer, definitivamente elegiría la primera opción.

Si desea dividir un número por 2, vaya 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-bitshift tiene menor precedencia que + o -, la división tiene mayor precedencia.

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

Simplemente use dividir (/), suponiendo que sea más claro. El compilador optimizará en consecuencia.

Estoy de acuerdo con otras respuestas que usted debe favorecer x / 2 porque su intención es más clara, y el compilador debe optimizarla 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 con signo y es negativo.

De la sección 6.5.7, viñeta 5 de la norma ISO C99:

El resultado de E1 >> E2 es E1 posiciones de bits desplazadas a la derecha E2. 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 con signo y un valor negativo, el valor resultante se define la implementación.

x / 2 es más claro, y x >> 1 no es mucho más rápido (según un micro-benchmark, alrededor de un 30% más rápido para una JVM Java). Como otros han señalado, 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 (aunque no pude verificar esto).

Incluso x / 2 no puede usar la instrucción (lenta) de la CPU de la división, porque algunos atajos son posibles, pero sigue siendo 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 está el desplazamiento a la derecha sin signo, x >>> 1, que es otra vez 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 matriz pueden ser muy grandes. Hubo un error en muchas versiones de búsqueda binaria, porque usaron (a + b) / 2 para calcular el promedio. Esto no funciona correctamente. La solución correcta es usar (a + b) >>> 1 en su lugar.)

Knuth dijo:

La optimización prematura es la raíz de todo mal.

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.

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 ver salidas del compilador en línea en godbolt.

Lo que se ve es que el compilador utiliza una instrucción sarl (aritmética de desplazamiento 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 para números negativos. Para hacer eso, cambia el bit de signo a el bit de orden más bajo, y agrega eso al resultado. Esto soluciona el problema de off-by-one al cambiar números negativos, en comparación con lo que haría una división.
Dado que el caso divide hace 2 cambios, 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 ensamblaje:

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

Del mismo modo para shift

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

Con salida:

    sarl    %edi
    movl    %edi, %eax
    ret

Solo una nota añadida -

X *= 0.5 a menudo será más rápido en algunos lenguajes basados en VM notably notablemente actionscript, ya que la variable no tendrá que ser comprobada para dividir por 0.

Use x = x / 2; O x /= 2; Porque es posible que un nuevo programador trabaje en él en el futuro. Así que será más fácil para él averiguar lo que está pasando en la línea de código. Todo el mundo puede no ser consciente de tales optimizaciones.

Estoy diciendo con el propósito de concursos de programación. Generalmente tienen entradas muy grandes donde la división por 2 tiene lugar muchas veces y se sabe que la entrada es positiva o negativa.

X>>1 será mejor que x/2. Lo comprobé. ideone.com ejecutando un programa donde se llevaron a cabo más de 10^10 operaciones de división por 2. x / 2 tomó casi 5.5 s mientras que x > > 1 tomó casi 2.6 s para el mismo programa.

Yo diría que hay varias cosas a considerar.

1. Bitshift debería ser más rápido, ya que ningún cálculo especial es realmente necesario para cambiar los bits, sin embargo, como se ha señalado, hay problemas potenciales con números negativos. Si usted está seguro de tener números positivos, y están buscando velocidad, entonces recomendaría bitshift.

2. El operador de división es muy fácil de leer para los humanos. Así que si usted está buscando la legibilidad del código, usted podría usar esto. Nota 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 leer y entender es una buena práctica.

3. Dependiendo del hardware subyacente, las operaciones pueden tener diferentes velocidades. La ley de Amdal es hacer que el caso común rápido. Así que usted puede tener hardware que puede realizar diferentes operaciones más rápido que otros. Por ejemplo, multiplicando por 0.5 puede ser más rápido que dividir por 2. (Concedido usted puede necesitar para tomar el piso de la multiplicación si desea imponer la división de enteros).

Si buscas rendimiento puro, te recomendaría crear algunas pruebas que podrían hacer las operaciones millones de veces. Muestra la ejecución varias veces (el tamaño de la muestra) para determinar cuál es estadísticamente mejor con tu sistema operativo/Hardware/Compilador/Código.

En lo que respecta a la CPU, las operaciones de desplazamiento de bits son más rápidas que las operaciones de división. Sin embargo, el compilador lo sabe y optimizará adecuadamente en la medida en que pueda, así que puede codificar de la manera que tenga más sentido y estar tranquilo sabiendo que su código es funcionando eficientemente. Pero recuerde que un unsigned int puede (en algunos casos) optimizarse mejor que un int por razones previamente señaladas. Si no necesita arithmatic firmado, entonces no incluya el bit de signo.

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

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

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

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

• Si está trabajando en un microcontrolador de 8 bits o cualquier cosa sin soporte de hardware para la multiplicación, el desplazamiento de bits es esperado y común, y mientras que el compilador casi seguramente convertirá x /= 2 en x >>= 1, la presencia de un símbolo de división levantará más cejas en ese entorno que usar un cambio para efectuar una división.
• Si está trabajando en un entorno de rendimiento crítico o sección de código, o su código podría ser compilado con la optimización del compilador desactivada, x >>= 1 con un comentario explicando su razonamiento es probablemente mejor solo para la 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. Mejor guardar el siguiente programador que pasa a mirar su código de la doble toma de 10 segundos en su operación de turno que para demostrar innecesariamente que sabía que el turno era más eficiente sans compiler optimización.

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

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

Generalmente el desplazamiento a la derecha 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 en un turno no te gana nada a expensas de la claridad.

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

Obviamente, si estás escribiendo tu código para el próximo tipo que lo lea, busca la claridad de "x/2".

Sin embargo, si la velocidad es tu objetivo, inténtalo en ambos sentidos y cronometra los resultados. Hace unos meses trabajé en una rutina de convolución de mapa de bits que implicaba 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 en realidad cronometré en ambos sentidos 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.

En términos de rendimiento. Las operaciones de cambio de CPU son significativamente más rápidas que los códigos de operación de división. Así dividiendo por dos o multiplicando por 2 etc todos los beneficios de las operaciones de cambio.

En cuanto a la apariencia. Como ingenieros, ¿cuándo nos apegamos tanto a los cosméticos que incluso las mujeres hermosas no usan? :)

X/Y es una correcta...y "> > " operador de cambio..si queremos dos dividir un entero podemos utilizar ( / ) operador dividendo. el operador shift se utiliza para desplazar los bits..

X = x/2; x/ = 2; podemos usar así..

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;
    }
}