Aprende en Comunidad
Avalados por :
Otimização de algoritmos: Potências de dois com 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.
Problema Statement: Dado um número, verificar se é uma potência positiva de dois ou não.
Primeiramente, gostaria de apresentar uma solução aritmética simples. Aqui está a solução na sintaxe de C, pois o problema do qual estamos falando é algorítmico e não orientado à linguagem. Além disso, todos poderão entender facilmente o fluxo do programa em 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 é um bom algoritmo de ordem O(log 2 n), ou seja, dado um número n, levará log 2 n operações para encontrar o resultado. Portanto, se n for 256, serão necessárias 8 operações para produzir o resultado. O algoritmo que desenvolvemos funciona a uma velocidade surpreendente. O(log 2 n) é um algoritmo muito eficiente. Ainda assim, se pudermos reduzi-lo ainda mais para O(1), seria ótimo, não é? Os operadores bit a bit vêm para o resgate.
Agora veja o programa abaixo, que é o algoritmo bit a bit para resolver o mesmo 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