C Programa para encontrar si un no es potencia de dos

Dado un entero positivo, escribe una función para encontrar si es una potencia de dos o no.
Ejemplos: 
 

Input : n = 4
Output : Yes
22 = 4

Input : n = 7
Output : No

Input : n = 32
Output : Yes
25 = 32

1. Un método simple para esto es simplemente tomar el logaritmo del número en base 2 y si obtienes un número entero, entonces el número es potencia de 2. 
 

// C Program to find whether a
// no is power of two
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
 
/* Function to check if x is power of 2*/
bool isPowerOfTwo(int n)
{
    return (ceil(log2(n)) == floor(log2(n)));
}
 
// Driver program
int main()
{
    isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n");
    isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n");
    return 0;
}
 
// This code is contributed by bibhudhendra

No
Yes

Complejidad del tiempo: O(log ₂ n)

Espacio Auxiliar: O(1)

2. Otra solución es seguir dividiendo el número por dos, es decir, hacer n = n/2 iterativamente. En cualquier iteración, si n%2 se vuelve distinto de cero y n no es 1, entonces n no es una potencia de 2. Si n se convierte en 1, entonces es una potencia de 2.
 

#include <stdbool.h>
#include <stdio.h>
 
/* Function to check if x is power of 2*/
bool isPowerOfTwo(int n)
{
    if (n == 0)
        return 0;
    while (n != 1) {
        if (n % 2 != 0)
            return 0;
        n = n / 2;
    }
    return 1;
}
 
/*Driver program to test above function*/
int main()
{
    isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n");
    isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n");
    return 0;
}

No
Yes

3. Todas las potencias de dos números tienen solo un conjunto de bits. Así que cuenta el no. de bits establecidos y si obtiene 1, entonces el número es una potencia de 2. Consulte Contar bits establecidos en un número entero para contar bits establecidos.
4. Si restamos una potencia de 2 números por 1, todos los bits no establecidos después del único bit establecido se establecerán; y el bit establecido se desactiva.
Por ejemplo, para 4 (100) y 16 (10000), obtenemos lo siguiente después de restar 1 
3 -> 011 
15 -> 01111
Entonces, si un número n es una potencia de 2, bit a bit & de n y n-1 será cero . Podemos decir que n es una potencia de 2 o no según el valor de n&(n-1). La expresión n&(n-1) no funcionará cuando n sea 0. Para manejar este caso también, nuestra expresión se convertirá en n& (!n&(n-1)) (gracias ahttps://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ Mohammad por agregar este caso). 
A continuación se muestra la implementación de este método. 
 

#include <stdio.h>
#define bool int
 
/* Function to check if x is power of 2*/
bool isPowerOfTwo(int x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x & (x - 1)));
}
 
/*Driver program to test above function*/
int main()
{
    isPowerOfTwo(31) ? printf("Yes\n") : printf("No\n");
    isPowerOfTwo(64) ? printf("Yes\n") : printf("No\n");
    return 0;
}

No
Yes

¡ Consulte el artículo completo sobre el programa para averiguar si un no es potencia de dos para obtener más detalles!