Aprende en Comunidad
Avalados por :
Optimización de algoritmos: Potencias de dos con operadores bit a bit
- Creado 01/03/2024
- Modificado 01/03/2024
- 1 Vistas
The power of bitwise operators is immense. Sometimes thinking in terms of arithmetical operators can cost you a lot of CPU time when compared to bitwise operators. So, when faced with a problem, it's obvious for us to think in terms of arithmetical solutions, but try to search for a bitwise solution and compare it with the previous one. You can end up with a very powerful algorithm too. Now I wish to share one such case where the use of bitwise operators avoids the use of a loop as well.
Enunciado del problema: Dado un número, verificar si es una potencia positiva de dos o no.
Primero me gustaría dar una solución aritmética simple. Aquí he dado la solución en la sintaxis de C ya que el problema del que estamos hablando es algorítmico y no orientado al lenguaje. Además, todos podrán entender fácilmente el flujo del programa en C.
int main()
{
int a=256,rem,flag=0;
while(a>1)
{
c=a%2;
if(c==1)
{
flag=1;
break;
}
a=a/2;
}
if(flag==1)
printf("Not Power of 2");
else
printf("Power of 2");
return 0;
}Este es un buen algoritmo de orden O(log 2 n), es decir, dado un número n, tomará log 2 n operaciones para encontrar el resultado. Entonces, si n es 256, se requieren 8 operaciones para producir el resultado. El algoritmo que hemos desarrollado funciona a una velocidad asombrosa. O(log 2 n) es un algoritmo muy bueno. Aún así, si se puede reducir aún más a O(1) sería genial, ¿verdad? Los operadores bit a bit vienen al rescate.
Ahora vea el programa a continuación que es el algoritmo bit a bit para resolver el mismo problema.
int main()
{
int a=256;
if((a&(a-1)==0)
printf("Power of 2");
else
printf("Not Power of 2");
return 0;
}
Sin respuestas
No hay respuestas para mostrar
Se el primero en responder
contacto@primeinstitute.com
(+51) 1641 9379
(+57) 1489 6964
© 2024 Copyright. Todos los derechos reservados.
Desarrollado por Prime Institute