¡Caminando hacia el éxito!

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
0
Cargando...

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;
}
Pedro Pascal
Se unió el 07/03/2018
Pinterest
Telegram
Linkedin
Whatsapp

Sin respuestas

No hay respuestas para mostrar 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

¡Hola! Soy Diana, asesora académica de Prime Institute, indícame en que curso estas interesado, saludos!
Hola ¿Puedo ayudarte?