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

406

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

Técnica 1:

x = x >> 1;

Técnica 2:

x = x / 2;

Aquí xhay un número entero.

Abhineet
fuente
75
Si realmente desea asignar el resultado xnuevamente, ninguno de los dos es apropiado de esta manera: debería ser cualquiera x >>= 1o x /= 2, dependiendo de lo que pretenda expresar con la operación. No porque sea más rápido (cualquier compilador moderno compilará todas las variantes equivalentes a un ensamblaje idéntico y rápido de todos modos) sino porque es menos confuso.
Leftaroundabout
33
No estoy de acuerdo con la izquierda alrededor. - Pero creo que es digno de mención que hay una operación llamada cambio aritmético en muchos lenguajes de programación que mantiene el bit de signo en su lugar y, por lo tanto, funciona para valores con signo como se esperaba. La sintaxis puede ser como x = x >>> 1. También tenga en cuenta que, dependiendo de la plataforma y el compilador, puede ser bastante razonable optimizar manualmente las divisiones y multiplicaciones usando turnos. - Pensando en microcontroladores, por ejemplo, sin soporte directo de ALU para la multiplicación.
JimmyB
36
Prefiero x /= 2porque se x >>= 1parece demasiado a la unión monádica;)
fredoverflow
19
@leftaroundabout: creo que es mucho más legible escribir en x = x / 2lugar de hacerlo x /= 2. Preferencia subjetiva quizás :)
JimmyB
8
@HannoBinder: ciertamente subjetivo, en particular mucha costumbre. OMI, en un lenguaje donde todos los operadores aritméticos tienen las ⬜=combinaciones, estas deberían usarse siempre que sea posible. Elimina el ruido y pone énfasis en el hecho de que xse modifica , mientras que el =operador general sugiere que adquiere un valor completamente nuevo independiente del anterior. - Siempre evitando los operadores combinados (para que sea legible por lo que alguien que sólo sabe operadores matemáticos) puede tener su punto así, pero entonces que había necesidad de renunciar a la extremadamente útil ++, --, +=, también.
Leftaroundabout

Respuestas:

847

Use la operación que mejor describa lo que está tratando de hacer.

  • Si está tratando el número como una secuencia de bits, use el desplazamiento de bits.
  • Si lo trata como un valor numérico, use 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

(ideona)

Mark Byers
fuente
20
La pregunta original también era vaga sobre el término "mejor". 'Mejor' en términos de velocidad, legibilidad, preguntas del examen para engañar a los estudiantes, etc. En ausencia de una explicación de lo que significa 'mejor', esta parece ser la respuesta más correcta.
Ray
47
En C ++ 03, ambas son implementaciones definidas para números negativos y pueden dar los mismos resultados. En C ++ 11, la división está bien definida para números negativos, pero el cambio todavía está definido por la implementación.
James Kanze
2
Mientras que la definición de / es implementación (si se redondea hacia arriba o hacia abajo para números negativos) definida en los primeros estándares de C. Siempre debe ser coherente con% (operador de módulo / resto).
ctrl-alt-delor
77
"Implementación definida" significa que el implementador del compilador debe elegir entre varias opciones de implementación, generalmente con restricciones sustanciales. Aquí, una restricción es que los operadores %y /deben ser consistentes para los operandos positivos y negativos, de modo que (a/b)*b+(a%b)==asea ​​cierto independientemente de los signos de ay b. Por lo general, el autor tomará decisiones para obtener el mejor rendimiento posible de la CPU.
RBerteig
66
Entonces, todos los que dicen "el compilador lo convertirá en un turno de todos modos" están equivocados, ¿verdad? A menos que el compilador pueda garantizarle que está tratando con un número entero no negativo (ya sea una constante o un int sin signo), no puede cambiarlo a un cambio
Kip
225

¿El primero parece dividir? No. Si quieres dividir, úsalo 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 hace por su cuenta.

Cat Plus Plus
fuente
15
Muchos compiladores no convertirán la división por potencia de dos en un cambio de bits. Esa sería una optimización incorrecta para enteros con signo. Debería intentar ver la salida del ensamblaje desde su compilador y ver por usted mismo.
exDM69
1
IIRC Utilicé eso para hacer que la reducción paralela sea más rápida en CUDA (evitar el número entero div). Sin embargo, esto fue hace más de un año, me pregunto qué tan inteligentes son los compiladores de CUDA hoy en día.
Nils
99
@ exDM69: Muchos compiladores lo harán incluso para enteros firmados, y solo los ajustarán de acuerdo con la firma. Una buena herramienta para jugar con estas cosas es esta: tinyurl.com/6uww253
PlasmaHH
19
@ exDM69: Y eso es relevante, ¿cómo? Dije "si es posible", no "siempre". Si la optimización es incorrecta, hacerlo manualmente no lo hace correcto (además, como se mencionó, GCC es lo suficientemente inteligente como para encontrar un reemplazo adecuado para los enteros con signo).
Cat Plus Plus
44
Mirando la página de WikiPedia, esto es aparentemente controvertido, pero no lo llamaría una reducción de fuerza. Una reducción de la fuerza es cuando, en un ciclo, se reduce, por ejemplo, de la multiplicación a la suma, al agregar valores anteriores en el ciclo. Esto es más una optimización de mirilla, que los compiladores pueden hacer de manera bastante confiable.
SomeCallMeTim
189

Para agregar: hay muchas razones para favorecer el uso. x = x / 2; Aquí hay algunas:

  • expresa su intención más claramente (suponiendo que no esté tratando con bits de registro de giro de bits o algo así)

  • el compilador reducirá esto a una operación de turno de todos modos

  • incluso si el compilador no lo redujo y eligió una operación más lenta que el cambio, la probabilidad de que esto termine afectando el rendimiento de su programa de una manera mensurable es en sí misma muy pequeña (y si lo afecta de manera medible, entonces tiene un valor real 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 aún más que el problema de precedencia mencionado anteriormente

  • para reiterar: el compilador ya lo hará por usted de todos modos. De hecho, convertirá la división por una constante en una serie de cambios, sumas y multiplicaciones para todo tipo de números, no solo potencias de dos. Vea esta pregunta para obtener enlaces a más información sobre esto.

En resumen, no compra nada codificando un turno cuando realmente quiere 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 era apropiado.

Michael Burr
fuente
55
También vale la pena agregar que si bien existen reglas de precedencia, no hay nada de malo en usar paréntesis. Mientras actualizaba algún código de producción, en realidad vi algo de la forma a/b/c*d(donde se a..ddenotaban las variables numéricas) en lugar de la mucho más legible (a*d)/(b*c).
1
El rendimiento y las optimizaciones dependen del compilador y el objetivo. Por ejemplo, hago un trabajo para un microcontrolador en el que cualquier cosa superior a -O0 está desactivada a menos que compre el compilador comercial, por lo que el compilador definitivamente no convertirá la división en cambios de bits. Además, los cambios de bits toman un ciclo y la división tarda 18 ciclos en este objetivo y, dado que la velocidad del reloj de los microcontroladores es bastante baja, esto puede ser un impacto notable en el rendimiento (pero depende de su código; definitivamente debe usar / hasta que el perfil le diga es un problema!)
44
@JackManey, si hay alguna posibilidad de que a*do b*cproduciría un desbordamiento, la forma menos legible no es equivalente y tiene una ventaja evidente. PD Estoy de acuerdo en que los paréntesis son tu mejor amigo.
Mark Ransom
@MarkRansom: un punto justo (a pesar de que me encontré con el a/b/c*dcódigo R, en un contexto donde el desbordamiento significaría que algo estaba mal con los datos, y no en, digamos, un bloque crítico de rendimiento del código C).
El código x=x/2;es solo "más claro" que x>>=1si xnunca será un número negativo impar o si a uno no le importan los errores ocasionales. De lo contrario x=x/2;y x>>=1;tienen diferentes significados. Si lo que uno necesita es el valor calculado por x>>=1, lo consideraría más claro que x = (x & ~1)/2o x = (x < 0) ? (x-1)/2 : x/2, o cualquier otra formulación que pueda pensar en usar la división por dos. Del mismo modo, si uno necesita el valor calculado por x/=2, eso es más claro que ((x + ((unsigned)x>>31)>>1).
supercat
62

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

Depende de lo que entiendas por 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 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 desplazamiento de bits tiene menor prioridad que +o -, la división tiene mayor prioridad.

Debe escribir su 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 micro optimizaciones.

Luchian Grigore
fuente
58

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

justin
fuente
34
El compilador debe optimizar en consecuencia.
Noctis Skytower
12
Si el compilador no se optimiza en consecuencia, debe usar un compilador mejor.
David Stone
3
@DavidStone: ¿En qué procesadores puede un compilador optimizar la división de un entero con signo posiblemente negativo por cualquier constante que no sea 1 para ser tan eficiente como un cambio?
supercat
1
@supercat: Ese es un buen punto. Por supuesto, podría almacenar el valor en un número entero sin signo (que creo que tiene una reputación mucho peor de la que deberían cuando se combina con advertencias de discrepancia firmadas / sin firmar), y la mayoría de los compiladores también tienen una forma de decirles que asuman que algo es cierto al optimizar . Preferiría envolver eso en una macro de compatibilidad y tener algo así como ASSUME(x >= 0); x /= 2;terminado x >>= 1;, pero ese sigue siendo un punto importante para mencionar.
David Stone el
39

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

Sin embargo, otra razón para preferir x / 2más x >> 1es que el comportamiento de >>depende de la implementación, si xes firmado, inty es negativo.

De la sección 6.5.7, viñeta 5 del estándar ISO C99:

El resultado de E1 >> E2es posiciones de bit E1desplazadas a la derecha E2. Si E1tiene un tipo sin signo o si E1tiene un tipo con signo y un valor no negativo, el valor del resultado es la parte integral del cociente de E1/ 2 E2. Si E1tiene un tipo con signo y un valor negativo, el valor resultante está definido por la implementación.

jamesdlin
fuente
3
Vale la pena señalar que el comportamiento que muchas implementaciones definen para x>>scalepowerlos números negativos será precisamente lo que se necesita al dividir un valor por una potencia de dos para fines tales como el renderizado de pantalla, mientras que el uso x/scalefactorserá incorrecto a menos que uno aplique correcciones a valores negativos.
supercat
32

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

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

(Esta es una C / C ++ cuestión, otros lenguajes de programación tienen más operadores. Para Java también es el desplazamiento sin signo de la derecha, x >>> 1que es de nuevo diferente. Permite calcular correctamente el valor medio (promedio) de dos valores, por lo que (a + b) >>> 1la voluntad devuelve el valor medio incluso para valores muy grandes de ay 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 la búsqueda binaria , porque solían (a + b) / 2calcular el promedio. no funciona correctamente. La solución correcta es usar (a + b) >>> 1en su lugar.)

Thomas Mueller
fuente
1
Los compiladores no pueden convertir x/2a x>>1en los casos en que xpueden ser negativas. Si lo que uno quiere es el valor que x>>1calcularía, seguramente será más rápido que cualquier expresión x/2que implique el mismo valor.
supercat
Tienes razón. Un compilador solo puede convertir x/2a x>>1si sabe que el valor no es negativo. Intentaré actualizar mi respuesta.
Thomas Mueller
sin divembargo, los compiladores aún evitan una instrucción al convertir x/2a (x + (x<0?1:0)) >> 1(donde >> es un desplazamiento aritmético a la derecha, que se desplaza en bits de signo). Esto requiere 4 instrucciones: copie el valor, shr (para obtener solo el bit de signo en un registro), agregue, sar. goo.gl/4F8Ms4
Peter Cordes
La pregunta está etiquetada como C y C ++.
Josh Sanford
22

Knuth dijo:

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

Entonces 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.

Ivan Californias
fuente
44
¿Cuál consideraría el método preferido para reducir un número por una potencia de dos si uno quiere que los números enteros mantengan el axioma (que se aplica a los números naturales y los números reales) que (n + d) / d = (n / d) + 1? Las violaciones de ese axioma al escalar gráficos causarán "costuras" visibles en el resultado. Si uno quiere algo que sea uniforme y casi simétrico respecto a cero, (n+8)>>4funciona bien. ¿Puede ofrecer algún enfoque que sea tan claro o eficiente sin utilizar un desplazamiento a la derecha firmado?
supercat
19

Echa un vistazo a la salida del compilador para ayudarte a decidir.
Ejecuté 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 ve es que el compilador utiliza una sarlinstrucción (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 los números negativos. Para hacerlo, desplaza el bit de signo hacia abajo al bit de orden más bajo y lo agrega al resultado. Esto soluciona el problema de uno por uno al cambiar los números negativos, en comparación con lo que haría una división.
Dado que 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 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

de manera similar para turno

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

con salida:

    sarl    %edi
    movl    %edi, %eax
    ret
Michael Donohue
fuente
Dependiendo de lo que uno esté haciendo, puede corregir el error de uno por uno, o puede causar un error de uno por uno (en comparación con lo que realmente se necesita) que requerirá el uso de más código para solucionarlo. Si lo que uno quiere es un resultado anulado, un desplazamiento a la derecha es más rápido y fácil que cualquier otra alternativa que conozca.
supercat
Si necesita un piso, es poco probable que describa lo que quiere como "dividir por 2"
Michael Donohue
La división de los números naturales y los números reales mantiene el axioma que (n + d) / d = (n / d) +1. La división de números reales también defiende (-n) / d = - (n / d), un axioma que no tiene sentido con los números naturales. No es posible tener un operador de división que esté cerrado en enteros y defienda ambos axiomas. En mi opinión, decir que el primer axioma debería ser válido para todos los números y el segundo solo para los reales parece más natural que decir que el primero debería ser válido para números enteros o reales, pero no para enteros. Además, tengo curiosidad sobre en qué casos el segundo axioma es realmente útil .
supercat
1
Un método de división entera que satisface el primer axioma dividirá la recta numérica en regiones de tamaño d. Dicha partición es útil para muchos propósitos. Incluso si uno prefiere tener el punto de interrupción en otro lugar que no sea entre 0 y -1, agregar un desplazamiento lo moverá. Una división entera que satisfaga el segundo axioma dividirá la recta numérica en regiones que son principalmente de tamaño d, pero una de las cuales es de tamaño 2*d-1. No exactamente divisiones "iguales". ¿Puedes ofrecer sugerencias de cuándo la partición de Oddball es realmente útil?
supercat
La salida del compilador para shr2signed es incorrecta. gcc en x86 elige implementar >> de enteros con signo con cambios aritméticos ( sar). goo.gl/KRgIkb . Esta publicación de la lista de correo ( gcc.gnu.org/ml/gcc/2000-04/msg00152.html ) confirma que gcc históricamente usa cambios aritméticos para entradas firmadas, por lo que es muy poco probable que FreeBSD gcc 4.2.1 use cambio sin firmar. Actualicé su publicación para corregir eso y el párrafo anterior que decía que ambos usaban shr, cuando en realidad es SAR que ambos usan. El SHR es cómo extrae el bit de signo para el /caso. También se incluye un enlace godbolt.
Peter Cordes
15

Solo una nota adicional:

x * = 0.5 a menudo será más rápido en algunos lenguajes basados ​​en VM, especialmente actionscript, ya que la variable no tendrá que verificarse para dividir por 0.

ansiart
fuente
2
@minitech: Esa es una prueba tan mala. Todo el código en la prueba es constante. Incluso antes de que el código sea JITED, eliminará todas las constantes.
@ M28: Estaba bastante seguro de que las partes internas de jsPerf (es decir eval) hacían que eso ocurriera de nuevo cada vez. De todos modos, sí, es una prueba bastante mala, porque es una optimización muy tonta.
Ry-
13

Use x = x / 2; O x /= 2;Porque es posible que un nuevo programador trabaje en él en el futuro. Entonces será más fácil para él descubrir qué está pasando en la línea de código. Es posible que todos no estén al tanto de tales optimizaciones.

Soy papá
fuente
12

Lo digo con el propósito de programar competencias. 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. Revisé ideone.com ejecutando un programa donde se llevaron a cabo más de 10 ^ 10 divisiones por 2 operaciones. x / 2 tomó casi 5.5s mientras que x >> 1 tomó casi 2.6s para el mismo programa.

Shashwat Kumar
fuente
1
Para valores sin signo, un compilador debe optimizar x/2a x>>1. Para los valores con signo, casi todas las implementaciones definen x>>1tener un significado que es equivalente x/2pero que se puede calcular más rápido cuando xes positivo y útilmente diferente de x/2cuando xes negativo.
supercat
12

Yo diría que hay varias cosas a considerar.

  1. 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ó, existen posibles problemas con los números negativos. Si tiene la seguridad de tener números positivos y está buscando velocidad, le recomendaría bitshift.

  2. El operador de división es muy fácil de leer para los humanos. Entonces, si está buscando legibilidad de código, podría 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 comprender 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 sea rápido. Por lo tanto, puede tener hardware que puede 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. (De acuerdo, es posible que deba tomar el piso de la multiplicación si desea forzar la división de enteros).

Si buscas un 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 estadísticamente mejor con su sistema operativo / hardware / compilador / código.

James Oravec
fuente
2
"Bitshift debería ser más rápido". los compiladores optimizarán las divisiones en cambios de bits
Trevor Hickey
Espero que lo hagan, pero a menos que tenga acceso a la fuente del compilador, no puede estar seguro :)
James Oravec
1
También recomendaría bitshift si la implementación de uno lo maneja de la manera más común y la forma en que uno quiere manejar los números negativos coincide con lo >>que sí coincide y lo que /no.
supercat el
12

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 se optimizará adecuadamente en la medida de lo posible, para que pueda codificar de la manera que tenga más sentido y estar tranquilo sabiendo que su código se ejecuta de manera eficiente. Pero recuerde que una unsigned intlata (en algunos casos) puede optimizarse mejor que una intpor las razones previamente señaladas. Si no necesita aritmética con signo, no incluya el bit de signo.

tylerl
fuente
11

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 desea producir.

Gooner
fuente
11

Haga sus intenciones más claras ... por ejemplo, si desea dividir, use x / 2 y deje 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.

Atul Kumar
fuente
10

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

  • Si está trabajando en un microcontrolador de 8 bits o nada sin soporte de hardware para la multiplicación, se espera desplazamiento de bits y común, y mientras el compilador es casi seguro que gire x /= 2en x >>= 1la presencia de un símbolo de división elevará más las cejas en ese ambiente de usando un cambio para efectuar una división.
  • Si está trabajando en un entorno de rendimiento crítico o en una sección de código, o su código podría compilarse con la optimización del compilador desactivada, x >>= 1con un comentario que explique que su razonamiento probablemente sea mejor solo por claridad de propósito.
  • Si no se encuentra en una de las condiciones anteriores, haga que su código sea más legible simplemente usando x /= 2. Es mejor salvar al siguiente programador que mira su código en la doble toma de 10 segundos en su operación de turno que demostrar innecesariamente que sabía que el cambio era más eficiente sin la optimización del compilador.

Todos estos suponen enteros sin signo. El cambio simple probablemente no sea lo que desea para firmar. Además, DanielH plantea un buen punto sobre el uso x *= 0.5de ciertos lenguajes como ActionScript.

gkimsey
fuente
8

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

circusdei
fuente
7

generalmente el desplazamiento a la derecha divide:

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

esto a veces se usa 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 te aporta nada a costa de la claridad .

Echa un vistazo a esta página desde la programación práctica de C ++.

Mouna Cheikhna
fuente
Si se quiere calcular el valor que, por ejemplo, (x+128)>>8se calcularía para valores xno cercanos al máximo, ¿cómo podría hacerlo concisamente sin un cambio? Tenga en cuenta que (x+128)/256no funcionará. ¿Conoces alguna buena expresión que lo hará?
supercat
7

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

Sin embargo, si la velocidad es su objetivo, pruébelo en ambos sentidos y cronometra los resultados. Hace unos meses trabajé en una rutina de convolución de mapa de bits que consistía en recorrer una serie de enteros y dividir cada elemento entre 2. Hice todo tipo de cosas para optimizarlo, incluido el viejo truco de sustituir "x >> 1" por "x / 2 ".

Cuando realmente 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.

Chris Bennet
fuente
4

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

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

Farjad
fuente
3

X / Y es el correcto ... y el operador de desplazamiento ">>" ... si queremos que dos dividan un entero, podemos usar el operador de dividendo (/). El operador shift se usa para cambiar los bits.

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

chico chocolate
fuente
0

Si bien 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;
    }
}
Darin
fuente