Dado um número inteiro positivo, escreva uma função para descobrir se é uma potência de dois ou não.

Exemplos :

Input : n = 4
Output : Yes
22 = 4

Input : n = 7
Output : No

Input : n = 32
Output : Yes
25 = 32

1. Um método simples para isso é simplesmente pegar o log do número na base 2 e, se você obtiver um inteiro, o número é uma potência de 2.

<?php
// PHP Program to find 
// whether a no is 
// power of two
  
// Function to check
// Log base 2
function Log2($x)
{
    return (log10($x) / 
            log10(2));
}
  
  
// Function to check
// if x is power of 2
function isPowerOfTwo($n)
{
    return (ceil(Log2($n)) == 
            floor(Log2($n)));
}
  
// Driver Code
if(isPowerOfTwo(31))
echo "Yes\n";
else
echo "No\n";
  
if(isPowerOfTwo(64))
echo "Yes\n";
else
echo "No\n";
      
// This code is contributed 
// by Sam007
?>

Não
sim

2. Outra solução é continuar dividindo o número por dois, ou seja, faça n = n / 2 iterativamente. Em qualquer iteração, se n% 2 se tornar diferente de zero en não for 1, então n não é uma potência de 2. Se n se tornar 1, então é uma potência de 2.

<?php
  
// Function to check if
// x is power of 2
function isPowerOfTwo($n)
{
if ($n == 0)
    return 0;
while ($n != 1)
{
    if ($n % 2 != 0)
        return 0;
    $n = $n / 2;
}
return 1;
}
  
// Driver Code
if(isPowerOfTwo(31))
    echo "Yes\n";
else
    echo "No\n";
  
if(isPowerOfTwo(64))
    echo "Yes\n";
else
    echo "No\n";
  
// This code is contributed 
// by Sam007
?>

Não
sim

3. Todas as potências de dois números têm apenas um conjunto de bits. Então conte o não. de conjuntos de bits e se você obtiver 1, o número é uma potência de 2. Consulte Contagem de conjuntos de bits em um inteiro para a contagem de conjuntos de bits.

4. Se subtrairmos uma potência de 2 números por 1, então todos os bits não configurados após o único bit configurado se tornarem configurados; e o bit definido torna-se não definido.

Por exemplo, para 4 (100) e 16 (10000), obtemos o seguinte após subtrair 1
3 -> 011
15 -> 01111

Portanto, se um número n for uma potência de 2, então & bit a bit de n e n-1 será zero. Podemos dizer que n é uma potência de 2 ou não com base no valor de n & (n-1). A expressão n & (n-1) não funcionará quando n for 0. Para lidar com este caso também, nossa expressão se tornará n & (! N & (n-1)) (graças a https://www.geeksforgeeks.org/program -para-descobrir-se-um-não-é-potência-de-dois / Mohammad por adicionar este caso).
Abaixo está a implementação deste método.

<?php
// PHP program to efficiently 
// check for power for 2
  
// Function to check if
// x is power of 2
function isPowerOfTwo ($x)
{
// First x in the below expression
// is for the case when x is 0 
return $x && (!($x & ($x - 1)));
}
  
// Driver Code
if(isPowerOfTwo(31))
    echo "Yes\n" ;
else
    echo "No\n";
  
if(isPowerOfTwo(64))
    echo "Yes\n" ;
else
    echo "No\n";
          
// This code is contributed by Sam007
?>

Não
sim

Consulte o artigo completo sobre o Programa para saber se um não é uma potência de dois para obter mais detalhes!