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

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?

(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.

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.

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 & (x−1));
}

Para mais detalhes, veja aqui .

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

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

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.

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));

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))

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));
}

return n > 0 && 0 == (1 << 30) % n;

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 .

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.

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));
}

É 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;
}

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));}

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

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)