Como verificar se um número é uma potência de 2

Hoje eu precisava de um algoritmo simples para verificar se um número é uma potência de 2.

O algoritmo precisa ser:

1. Simples
2. Correto para qualquer ulongvalor.

Eu vim com este algoritmo simples:

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

Mas então pensei: que tal verificar se é um número exatamente redondo? Mas quando verifiquei 2 ^ 63 + 1, retornei exatamente 63 por causa do arredondamento. Então eu verifiquei se 2 na potência 63 é igual ao número original - e é, porque o cálculo é feito em se não em números exatos:log2 xMath.Logdouble

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

Este voltou truepara o valor errado: 9223372036854775809.

Existe um algoritmo melhor?

Há um truque simples para esse problema:

bool IsPowerOfTwo(ulong x)
{
    return (x & (x - 1)) == 0;
}

Observe que esta função reportará truepara 0, o que não é uma potência de 2. Se você deseja excluir isso, veja como:

bool IsPowerOfTwo(ulong x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Explicação

Em primeiro lugar, o binário e operador bit a bit da definição do MSDN:

Binário e operadores são predefinidos para os tipos integrais e bool. Para tipos integrais, & calcula o AND lógico bit a bit de seus operandos. Para operandos booleanos, & calcula o AND lógico de seus operandos; isto é, o resultado é verdadeiro se e somente se ambos os seus operandos forem verdadeiros.

Agora vamos dar uma olhada em como tudo isso acontece:

A função retorna booleano (verdadeiro / falso) e aceita um parâmetro de entrada do tipo não assinado por muito tempo (x, neste caso). Por uma questão de simplicidade, suponha que alguém tenha passado o valor 4 e chamado a função da seguinte maneira:

bool b = IsPowerOfTwo(4)

Agora substituímos cada ocorrência de x por 4:

return (4 != 0) && ((4 & (4-1)) == 0);

Bem, nós já sabemos que 4! = 0 evals para true, até agora tudo bem. Mas e quanto a:

((4 & (4-1)) == 0)

Isso se traduz no seguinte:

((4 & 3) == 0)

Mas o que exatamente é 4&3?

A representação binária de 4 é 100 e a representação binária de 3 é 011 (lembre-se de & assume a representação binária desses números). Então nós temos:

100 = 4
011 = 3

Imagine esses valores sendo empilhados de maneira semelhante à adição elementar. O &operador diz que, se ambos os valores são iguais a 1, então o resultado é 1, caso contrário é 0. Assim 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, e 0 & 1 = 0. Então, fazemos as contas:

100
011
----
000

O resultado é simplesmente 0. Então, voltamos e olhamos para o que nossa declaração de retorno agora se traduz em:

return (4 != 0) && ((4 & 3) == 0);

Que agora se traduz em:

return true && (0 == 0);

return true && true;

Todos sabemos que true && trueé simples true, e isso mostra que, para o nosso exemplo, 4 é uma potência de 2.

Alguns sites que documentam e explicam esse e outros hacks de manipulação de bits são:

• http://graphics.stanford.edu/~seander/bithacks.html
  ( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 )
• http://bits.stephan-brumme.com/
  ( http://bits.stephan-brumme.com/isPowerOfTwo.html )

E o avô deles, o livro "O prazer do hacker", de Henry Warren, Jr .:

• http://www.hackersdelight.org/

Como a página de Sean Anderson explica, a expressão ((x & (x - 1)) == 0)indica incorretamente que 0 é uma potência de 2. Ele sugere usar:

(!(x & (x - 1)) && x)

para corrigir esse problema.

return (i & -i) == i

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

Eu escrevi um artigo sobre isso recentemente em http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Ele cobre a contagem de bits, como usar os logaritmos corretamente, a verificação clássica "x &&! (X & (x - 1))" e outros.

Aqui está uma solução simples em C ++ :

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

O seguinte adendo à resposta aceita pode ser útil para algumas pessoas:

Uma potência de dois, quando expressa em binário, sempre se parecerá com 1 seguida por n zeros em que n é maior ou igual a 0. Ex:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

e assim por diante.

Quando subtraímos 1esses tipos de números, eles se tornam 0 seguidos por n e novamente n é o mesmo que acima. Ex:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

e assim por diante.

Chegando ao ponto crucial

O que acontece quando fazemos um AND bit a bit x, que é uma potência de 2, e x - 1?

O de xse alinha com o zero de x - 1e todos os zeros de xse alinham com os de x - 1, fazendo com que o E bit a bit resulte em 0. E é assim que temos a resposta de linha única mencionada acima correta.

Aumentando ainda mais a beleza da resposta aceita acima -

Portanto, agora temos uma propriedade à nossa disposição:

Quando subtraímos 1 de qualquer número, na representação binária o 1 mais à direita se tornará 0 e todos os zeros antes desse 1 mais à direita se tornarão 1

Um uso impressionante dessa propriedade é descobrir - quantos 1s estão presentes na representação binária de um determinado número? O código curto e suave para fazer isso para um determinado número inteiro xé:

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

Outro aspecto dos números que pode ser provado a partir do conceito explicado acima é "Todo número positivo pode ser representado como a soma das potências de 2?".

Sim, todo número positivo pode ser representado como a soma das potências de 2. Para qualquer número, considere sua representação binária. Ex: pegue o número 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

Depois de postar a pergunta, pensei na seguinte solução:

Precisamos verificar se exatamente um dos dígitos binários é um. Então, simplesmente mudamos o número para a direita, um dígito de cada vez, e retornamos truese for igual a 1. Se a qualquer momento chegarmos a um número ímpar ( (number & 1) == 1), sabemos que o resultado é false. Isso provou (usando uma referência) um pouco mais rápido que o método original para valores verdadeiros (grandes) e muito mais rápido para valores falsos ou pequenos.

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

Obviamente, a solução de Greg é muito melhor.

    bool IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

E aqui está um algoritmo geral para descobrir se um número é uma potência de outro número.

    bool IsPowerOf(int n,int b)
    {
        if (n > 1)
        {
            while (n % b == 0)
            {
                n /= b;
            }
        }
        return n == 1;
    }

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

Descubra se o número fornecido é uma potência de 2.

#include <math.h>

int main(void)
{
    int n,logval,powval;
    printf("Enter a number to find whether it is s power of 2\n");
    scanf("%d",&n);
    logval=log(n)/log(2);
    powval=pow(2,logval);

    if(powval==n)
        printf("The number is a power of 2");
    else
        printf("The number is not a power of 2");

    getch();
    return 0;
}

bool isPowerOfTwo(int x_)
{
  register int bitpos, bitpos2;
  asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
  asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
  return bitpos > 0 && bitpos == bitpos2;
}

int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

Isso é realmente rápido. Demora cerca de 6 minutos e 43 segundos para verificar todos os 2 ^ 32 números inteiros.

return ((x != 0) && !(x & (x - 1)));

Se xfor uma potência de dois, seu único bit 1 está em posição n. Isso significa que x – 1tem um 0 na posição n. Para entender por que, lembre-se de como uma subtração binária funciona. Ao subtrair 1 de x, o empréstimo se propaga até a posição n; o bit npassa a 0 e todos os bits inferiores passam a 1. Agora, como xnão possui 1 bit em comum com x – 1, x & (x – 1)é 0 e !(x & (x – 1))é verdadeiro.

Um número é uma potência de 2 se contiver apenas 1 bit definido. Podemos usar essa propriedade e a função genéricacountSetBits para descobrir se um número é 2 ou não.

Este é um programa C ++:

int countSetBits(int n)
{
        int c = 0;
        while(n)
        {
                c += 1;
                n  = n & (n-1);
        }
        return c;
}

bool isPowerOfTwo(int n)
{        
        return (countSetBits(n)==1);
}
int main()
{
    int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
    for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
        printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
    return 0;
}

Não precisamos verificar explicitamente se 0 é uma potência de 2, pois retorna False para 0 também.

RESULTADO

Num:0   Set Bits:0   is power of two: 0
Num:1   Set Bits:1   is power of two: 1
Num:2   Set Bits:1   is power of two: 1
Num:3   Set Bits:2   is power of two: 0
Num:4   Set Bits:1   is power of two: 1
Num:5   Set Bits:2   is power of two: 0
Num:15  Set Bits:4   is power of two: 0
Num:16  Set Bits:1   is power of two: 1
Num:22  Set Bits:3   is power of two: 0
Num:32  Set Bits:1   is power of two: 1
Num:38  Set Bits:3   is power of two: 0
Num:64  Set Bits:1   is power of two: 1
Num:70  Set Bits:3   is power of two: 0

Aqui está outro método que eu criei, neste caso usando em |vez de &:

bool is_power_of_2(ulong x) {
    if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
    return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

para qualquer potência de 2, o seguinte também é válido.

n & (- n) == n

OBSERVAÇÃO: falha para n = 0, portanto, é necessário verificar a
razão. Isso explica por que:
-n é o complemento 2s de n. -n terá todos os bits à esquerda do bit mais à direita definido de n invertido em comparação com n. Para potências de 2, existe apenas um bit definido.

Exemplo

0000 0001    Yes
0001 0001    No

Algoritmo

1. Usando uma máscara de bit, divida NUMa variável em binário

2. IF R > 0 AND L > 0: Return FALSE

3. Caso contrário, NUMtorna-se diferente de zero

4. IF NUM = 1: Return TRUE

5. Caso contrário, vá para a Etapa 1

Complexidade

Hora ~ O(log(d))onde dé o número de dígitos binários

Melhorando a resposta de @ user134548, sem bits aritméticos:

public static bool IsPowerOfTwo(ulong n)
{
    if (n % 2 != 0) return false;  // is odd (can't be power of 2)

    double exp = Math.Log(n, 2);
    if (exp != Math.Floor(exp)) return false;  // if exp is not integer, n can't be power
    return Math.Pow(2, exp) == n;
}

Isso funciona bem para:

IsPowerOfTwo(9223372036854775809)

Mark Gravell sugeriu isso se você tiver o .NET Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

Instrução única, mais rápida do que (x != 0) && ((x & (x - 1)) == 0)mas menos portátil.

Em C, testei o i && !(i & (i - 1)truque e o comparei com__builtin_popcount(i) , usando gcc no Linux, com o sinalizador -mpopcnt para garantir o uso da instrução POPCNT da CPU. Meu programa de teste contou o número de números inteiros entre 0 e 2 ^ 31 que eram uma potência de dois.

No começo, pensei que i && !(i & (i - 1)era 10% mais rápido, apesar de ter verificado que o POPCNT era usado na desmontagem em que eu usava__builtin_popcount .

No entanto, percebi que havia incluído uma instrução if, e a previsão de ramificação provavelmente estava se saindo melhor na versão de twiddling. Eu removi o if e o POPCNT acabou mais rápido, conforme o esperado.

Resultados:

CPU Intel (R) Core (TM) i7-4771 no máximo 3,90GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

Processador AMD Ryzen Threadripper 2950X de 16 núcleos, máximo de 3,50 GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

Observe que aqui o CPU Intel parece um pouco mais lento que o AMD com o bit girando, mas possui um POPCNT muito mais rápido; o AMD POPCNT não oferece tanto impulso.

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

Execute testes:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

Vejo muitas respostas sugerindo retornar n &&! (N & (n - 1)), mas, para minha experiência, se os valores de entrada forem negativos, ele retornará valores falsos. Compartilharei outra abordagem simples aqui, pois sabemos que uma potência de dois números tem apenas um bit definido; portanto, simplesmente contaremos o número de bits definido, isso levará tempo O (log N).

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

Verifique este artigo para contar não. de bits definidos

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

Este programa em java retorna "true" se número for uma potência de 2 e retorna "false" se não for uma potência de 2

// To check if the given number is power of 2

import java.util.Scanner;

public class PowerOfTwo {
    int n;
    void solve() {
        while(true) {
//          To eleminate the odd numbers
            if((n%2)!= 0){
                System.out.println("false");
                break;
            }
//  Tracing the number back till 2
            n = n/2;
//  2/2 gives one so condition should be 1
            if(n == 1) {
                System.out.println("true");
                break;
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        PowerOfTwo obj = new PowerOfTwo();
        obj.n = in.nextInt();
        obj.solve();
    }

}

OUTPUT : 
34
false

16
true