Qual é a maneira mais simples de testar se um número é uma potência de 2 em C ++?

94

Preciso de uma função como esta:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

Alguém pode sugerir como eu poderia escrever isso? Você pode me dizer um bom site onde esse tipo de algoritmo pode ser encontrado?

Formiga
fonte
@rootTraveller - Provavelmente não é uma duplicata. C ++ e Java são linguagens diferentes e cada uma oferece recursos diferentes. Por exemplo, em C / C ++ podemos agora usar intrínsecos com processadores habilitados para IMC, o que emite a instrução da máquina para fazer isso em uma única hora. Imagino que Java tenha outras coisas, como talvez algo de uma rotina matemática.
jww

Respostas:

190

(n & (n - 1)) == 0é melhor. No entanto, observe que ele retornará verdadeiro incorretamente para n = 0, portanto, se isso for possível, você desejará verificar isso explicitamente.

http://www.graphics.stanford.edu/~seander/bithacks.html tem uma grande coleção de algoritmos de bit-twiddling inteligentes, incluindo este.

Anônimo
fonte
8
então, basicamente(n>0 && ((n & (n-1)) == 0))
Saurabh Goyal
1
@SaurabhGoyal ou n && !(n & (n - 1))como o link nos estados de resposta.
Carsten
Por que, ah, por que isso não está no topo das respostas? OP, por favor aceite.
donturner
@SaurabhGoyal Uma melhoria pequena é esta: n & !(n & (n - 1)). Observe o AND bit a bit &(não lógico e &&). Operadores bit a bit não implementam curto-circuito e, portanto, o código não se ramifica. Isso é preferível em situações em que as previsões erradas dos ramos são prováveis ​​e quando o cálculo do rhs da expressão (ou seja, !(n & (n - 1))) é barato.
Cassio Neri de
@cassio !é um operador lógico e, portanto, o valor de !(n & (n - 1))seria um booleano. Tem certeza de que um booleano e um número podem ser dados a um operador AND bit a bit? Se sim, parece bom.
Saurabh Goyal
81

Uma potência de dois terá apenas um conjunto de bits (para números sem sinal). Algo como

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Funcionará bem; um a menos que a potência de dois é todo 1s nos bits menos significativos, então deve fazer AND para 0 bit a bit.

Como eu estava assumindo números sem sinal, o teste == 0 (que originalmente esqueci, desculpe) é adequado. Você pode querer um teste> 0 se estiver usando números inteiros com sinal.

Adam Wright
fonte
Está faltando um '!' ou um '== 0'
Você também está perdendo um teste para o valor negativo de x.
Rob Wells de
Legal, como você editou sem que "editado x minutos atrás" apareça?
Sério, como você conseguiu 120 repetições para uma resposta comprovadamente errada?
@Mike F: Na verdade, parece que as pessoas vão votar nas respostas sem verificá-las. Qualquer um pode cometer um erro, eu acho - se eu cometer algum no futuro, fique à vontade para editá-los.
Adam Wright de
49

Potências de dois em binário são assim:

1: 0001
2: 0010
4: 0100
8: 1000

Observe que sempre há exatamente 1 bit definido. A única exceção é com um número inteiro assinado. por exemplo, um inteiro assinado de 8 bits com um valor de -128 se parece com:

10000000

Assim, depois de verificar se o número é maior que zero, podemos usar um pequeno truque inteligente para testar se um e apenas um bit está definido.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x1));
}

Para mais detalhes, veja aqui .

Matt Howells
fonte
14

Abordagem # 1:

Divida o número por 2 reclusivamente para verificá-lo.

Complexidade de tempo: O (log2n).

Abordagem # 2:

E o número bit a bit com seu número anterior deve ser igual a ZERO.

Exemplo: Número = 8 Binário de 8: 1 0 0 0 Binário de 7: 0 1 1 1 e o AND bit a bit de ambos os números é 0 0 0 0 = 0.

Complexidade de tempo: O (1).

Abordagem # 3:

XOR bit a bit o número com seu número anterior deve ser a soma de ambos os números.

Exemplo: Número = 8 Binário de 8: 1 0 0 0 Binário de 7: 0 1 1 1 e o XOR bit a bit de ambos os números é 1 1 1 1 = 15.

Complexidade de tempo: O (1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

Raj Dixit
fonte
8
bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}
Rob Wells
fonte
7

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

n & (- n) == n

NOTA: A condição é verdadeira para n = 0, embora não seja uma potência de 2. A
razão pela qual isso funciona é:
-n é o complemento de 2s de n. -n terá cada bit à esquerda do bit definido mais à direita de n invertido em comparação com n. Para potências de 2, há apenas um bit definido.

FReeze FRancis
fonte
2
eu quis dizer que a condição é verdadeira para n = 0, embora não seja potência de dois
FReeze FRancis
isso funciona com as conversões que acontecem se n não tiver sinal?
Joseph Garvin
5

Em C ++ 20, existe o std::ispow2que você pode usar exatamente para essa finalidade se não precisar implementá-lo sozinho:

#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));
Rakete1111
fonte
5

Este é provavelmente o mais rápido, se estiver usando o GCC. Ele usa apenas uma instrução de cpu POPCNT e uma comparação. Representação binária de qualquer potência de 2 números, tem sempre apenas um conjunto de bits, os outros bits são sempre zero. Assim, contamos o número de bits definidos com POPCNT e, se for igual a 1, o número é a potência de 2. Não acho que haja métodos mais rápidos possíveis. E é muito simples, se você entendeu uma vez:

if(1==__builtin_popcount(n))
F10PPY
fonte
Não. Acabei de testar isso. Eu amo popcount, mas para o teste de potência de 2, o teste i && !(i & (i - 1)))é cerca de 10% mais rápido na minha máquina, mesmo quando eu tinha certeza de habilitar a instrução POPCNT de assembly nativo no gcc.
eraoul
Opa, eu retiro. Meu programa de teste estava rodando em um loop e a previsão do branch era "trapaça". Você está certo, se você tiver a instrução POPCNT em sua CPU, ela é mais rápida.
eraoul
3

Seguir seria mais rápido do que a resposta mais votada devido ao curto-circuito booleano e ao fato de que a comparação é lenta.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x  1));
}

Se você sabe que x não pode ser 0, então

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x  1));
}
Margus
fonte
3
return n > 0 && 0 == (1 << 30) % n;
Yuxiang Zhang
fonte
3

Qual é a maneira mais simples de testar se um número é uma potência de 2 em C ++?

Se você tiver um processador Intel moderno com as instruções de manipulação de bits , poderá executar o seguinte. Omite o código C / C ++ direto porque outros já responderam, mas você precisa dele se o IMC não estiver disponível ou ativado.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

GCC, ICC e Clang sinalizam suporte para IMC com __BMI__. Ele está disponível em compiladores da Microsoft no Visual Studio 2015 e superior quando o AVX2 está disponível e ativado . Para os cabeçalhos de que você precisa, consulte Arquivos de cabeçalho para intrínsecos SIMD .

Eu normalmente guardo o _blsr_u64com um _LP64_caso compilando em i686. O Clang precisa de uma pequena solução alternativa porque usa um nome de símbolo intrínseco ligeiramente diferente:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

Você pode me dizer um bom site onde esse tipo de algoritmo pode ser encontrado?

Este site é frequentemente citado: Bit Twiddling Hacks .

jww
fonte
Certamente, esta não é a "maneira mais simples" conforme solicitado no OP, mas sem dúvida a mais rápida para ambientes específicos. Mostrar como condicionar para diferentes arquiteturas é extremamente útil.
fearless_fool
1

Este não é o caminho mais rápido ou curto, mas acho que é muito legível. Então, eu faria algo assim:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

Isso funciona porque o binário é baseado em potências de dois. Qualquer número com apenas um bit definido deve ser uma potência de dois.

Jere.Jones
fonte
Pode não ser rápido ou curto, mas está correto ao contrário das principais respostas.
2
Na hora de comentar estavam todos grampeados. Desde então, eles foram editados em um estado aceitável.
0

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

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}
Chethan
fonte
0

É possível através de c ++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}
Jay Ponkia
fonte
2
Isso não é simples nem rápido para mim.
luk32 de
2
Ou seja, certamente não é rápido devido a log2, e a prova de que funciona não é tão fácil de explicar (precisamente, você pode ser pego por erros de arredondamento?). Também é desnecessariamente complicado com if..return..else..return. O que há de errado em reduzi-lo return x==(double)y;? Ele deve retornar boolanyayws. O IMO, mesmo o operador ternário, seria mais claro se alguém realmente quiser mantê-lo int.
luk32
0

Sei que este é um post muito antigo, mas achei que poderia ser interessante postar aqui.


Da Code-Golf SE (portanto, todos os créditos para quem escreveu isso): Showcase of Languages

(Parágrafo sobre C , parágrafo Comprimento 36 fragmento )

bool isPow2(const unsigned int num){return!!num&!(num&(num-1));}
Erel
fonte
-1

Outra maneira (talvez não mais rápida) é determinar se ln (x) / ln (2) é um número inteiro.

MikeJ
fonte
2
Não há talvez sobre isso :-).
paxdiablo de
1
Isso teria problemas com imprecisão de ponto flutuante. ln (1 << 29) / ln (2) resulta em 29,000000000000004.
Anônimo de
-3

Este é o método bit-shift em T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

É muito mais rápido do que fazer um logaritmo quatro vezes (primeiro conjunto para obter o resultado decimal, segundo conjunto para obter conjunto inteiro e comparar)

Jesse Roberge
fonte
5
É bom ver como a resposta principal a essa pergunta também pode ser implementada no T-SQL, mas isso não é realmente relevante para a pergunta feita aqui. Uma alternativa (se você estava procurando por uma solução em T-SQL, encontrou esta pergunta respondida, implementou em T-SQL e achou interessante postar esta resposta) seria postar a pergunta com referência a T-SQL, então responda você mesmo, com referência a esta pergunta respondida. Espero que esta sugestão seja útil.
Simon
isso realmente não responde a esta pergunta
phuclv