2009-06-27 13 views
7

Recientemente descubrí, que si necesito ver si la variable es par (o impar), podría ver si el último bit de la variable es igual a 0. Este descubrimiento, cuando se implementó, reemplazó unos pocos módulo 2 cálculos y por lo tanto, todo la función funcionó más rápido.Verificando si el número es par mirando el último bit - ¿hay algún otro "truco" como este?

¿Hay algún otro "truco" como este, donde trabajar con bits podría reemplazar otros cálculos, lo que llevaría a un mejor tiempo de ejecución de la función?

+6

que podría haber ganado el mismo aumento de velocidad al permitir que las optimizaciones del compilador. Ese es un "truco" mucho más valioso. No pierda su tiempo en optimizaciones fácilmente automatizadas. El compilador hará eso por usted de todos modos – jalf

+0

@jalf - gracias por la idea de habilitar optimizaciones. No tengo experiencia y recién comencé a aprender C++. Tendré en mente tu sugerencia. – zeroDivisible

Respuesta

22

Dudo que la sustitución del uso de módulo dos cálculos por la operación en modo bit equivalente produce tiempos de ejecución más rápidos. Cualquier compilador de C++ que merezca su grano de arena compilará n % 2 y n & 1 con instrucciones idénticas de la máquina.

Tenga cuidado con el uso de hacks de intercambio de bits como una optimización. En primer lugar, no siempre es claro que la función que está optimizando es un cuello de botella. En segundo lugar, el código resultante suele ser más difícil de mantener y es más probable que sea incorrecto o tenga errores sutiles.Esto es lo que se entiende en la famosa cita de Knuth "Deberíamos olvidarnos de las pequeñas eficiencias, digamos el 97% de las veces: la optimización prematura es la raíz de todo mal". Ahorra tu esfuerzo

Si realmente debe seguir con este tema, Bit Twiddling Hacks contiene una buena lista de hacks interesantes.

1

Puede ser útil tener en cuenta que cuando C++ ve una operación modulo 2 como %2, generalmente se optimiza sin que usted realice operaciones a nivel de bit.

Si bien sería esclarecedor para entender todos estos trucos, debería ser agradable saber que el compilador (o el escritor del compilador) hace un gran esfuerzo para obtener todas las optimizaciones posibles.

Lo que debe recordar es que si usa constantes y trabaja en potencias de 2, las optimizaciones son más probables ya que los compiladores aprovechan las capacidades del operador binario de la máquina.


Además, sugiero que conozcan cómo funcionan los sistemas a bajo nivel.

Para este fin, los trucos de aprendizaje que se refieren aquí serían very useful.
Sin embargo, cryptic coding with complicated operations jammed together
(por ejemplo, para hacerlo todo en un menor número de bytes de código fuente) no es bueno.

Puede ser bueno saber que puede intercambiar dos variables de 32 bits 'en su lugar', sin una tercera variable temporal, usando operaciones XOR. Sin embargo, sería mucho más útil saber hhow cross compilation requires big-endian and little-endian handling para variables de 2/4 bytes ybit fields.

Hablando de campos de bits, me recuerda a otro stackoverflow conversation on their popularity. También sería una buena lectura (aunque no del todo relacionada con su pregunta).


En resumen, estoy totalmente de acuerdo con usted para aprender qué trucos se pueden hacer. Quiero usarlos para hacer que mi código tenga un mejor rendimiento, y creo firmemente que habrá conceptos como, what can programmers to do make better cache optimization, por ejemplo, que ayudarán a hacer mejores implementaciones.

3

Hay muchos. Una "colección" en línea con la que puede comenzar es http://www-graphics.stanford.edu/~seander/bithacks.html

Recomendaría muchísimo utilizar trucos de bits en el código a menos que el aumento de rendimiento sea absolutamente necesario. Estos trucos son muy ilegibles y tienen la sensación de que "de ninguna manera esto funciona", así que cuando intentas descubrir un error, son eficientes en el tiempo para quien sea que esté intentando depurar el código.

1

Aquí hay un buen truco. Al almacenar una fecha en un campo de base de datos que requiere una búsqueda intensa, no almacene la fecha en formato de fecha, en su lugar, guárdela como un entero en formato AAAAMMDD. Las bases de datos pueden buscar enteros mucho más rápido que las estructuras de fecha.

Cuestiones relacionadas