¿La multiplicación y división usando operadores de desplazamiento en C es realmente más rápida?
La multiplicación y división se pueden lograr utilizando operadores de bits, por ejemplo
i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)
etcétera.
¿Es realmente más rápido usar, por ejemplo, (i<<3)+(i<<1)multiplicar por 10 que usarlo i*10directamente? ¿Existe algún tipo de entrada que no se pueda multiplicar o dividir de esta manera?
Respuesta corta: No es probable.
Respuesta larga: su compilador tiene un optimizador que sabe cómo multiplicarse tan rápido como lo permite la arquitectura de su procesador de destino. Lo mejor que puede hacer es decirle claramente al compilador su intención (es decir, i*2 en lugar de i << 1) y dejar que decida cuál es la secuencia de código ensamblador/máquina más rápida. Incluso es posible que el propio procesador haya implementado la instrucción de multiplicación como una secuencia de cambios y sumas en el microcódigo.
En pocas palabras: no pierda mucho tiempo preocupándose por esto. Si quieres cambiar, cambia. Si quieres multiplicar, multiplica. Haga lo que sea semánticamente más claro: sus compañeros de trabajo se lo agradecerán más tarde. O, más probablemente, te maldiga más tarde si haces lo contrario.
Sólo un punto de medida concreto: hace muchos años, comparé dos versiones de mi algoritmo hash:
unsigned
hash( char const* s )
{
unsigned h = 0;
while ( *s != '\0' ) {
h = 127 * h + (unsigned char)*s;
++ s;
}
return h;
}
y
unsigned
hash( char const* s )
{
unsigned h = 0;
while ( *s != '\0' ) {
h = (h << 7) - h + (unsigned char)*s;
++ s;
}
return h;
}
En cada máquina en la que lo comparé, la primera fue al menos tan rápida como la segunda. Sorprendentemente, a veces era más rápido (por ejemplo, en un Sun Sparc). Cuando el hardware no admitía la multiplicación rápida (y la mayoría no lo hacía en aquel entonces), el compilador convertía la multiplicación en las combinaciones apropiadas de turnos y suma/sub. Y como conocía el objetivo final, a veces podía hacerlo con menos instrucciones que cuando se escribían explícitamente los turnos y los complementos/sustituciones.
Tenga en cuenta que esto fue hace unos 15 años. Con suerte, los compiladores solo han mejorado desde entonces, por lo que puedes contar con que el compilador hará lo correcto, probablemente mejor que tú. (Además, la razón por la que el código se ve tan C'ish es porque fue hace más de 15 años. Obviamente, std::stringhoy usaría iteradores and).
Además de todas las otras buenas respuestas aquí, permítanme señalar otra razón para no usar shift cuando se refiere a dividir o multiplicar. Nunca he visto a alguien introducir un error al olvidar la precedencia relativa de la multiplicación y la suma. He visto errores introducidos cuando los programadores de mantenimiento olvidaron que "multiplicar" mediante un cambio es lógicamente una multiplicación pero no sintácticamente tiene la misma precedencia que la multiplicación. x * 2 + zy x << 1 + zson muy diferentes!
Si está trabajando con números , utilice operadores aritméticos como + - * / %. Si está trabajando con matrices de bits, utilice operadores de manipulación de bits como & ^ | >>. No los mezcles; una expresión que tiene tanto trucos como aritmética es un error a punto de ocurrir.
Esto depende del procesador y del compilador. Algunos compiladores ya optimizan el código de esta manera, otros no. Por lo tanto, debe verificar cada vez que su código deba optimizarse de esta manera.
A menos que necesite desesperadamente optimizar, no codificaría mi código fuente solo para guardar una instrucción de ensamblaje o un ciclo de procesador.
