Power of Two
Você recebe um número inteiro n. Retorne true se n for uma potência de dois, ou seja, n = 2^k para algum número inteiro k ≥ 0, e false caso contrário. Portanto, 1, 2, 4 e 8 contam, enquanto 0, 6 e todos os números negativos não contam.
Função
- ninteger
- o inteiro a ser testado, que pode ser zero ou negativo
- Retornaboolean
- true se n for igual a 2^k para algum k ≥ 0, false caso contrário
Restrições
-231 ≤ n ≤ 231-1
Exemplos
- Entrada
- n = 16
- Saída
- true
- Explicação
- 16 = 2 × 2 × 2 × 2 = 2^4. Em binário, é
10000, um único bit 1.
- Entrada
- n = 24
- Saída
- false
- Explicação
- 24 = 8 × 3. Dividir pela metade resulta em 12, 6 e depois 3, que é ímpar, mas não 1. Em binário, 24 é
11000, dois bits 1.
- Entrada
- n = 1
- Saída
- true
- Explicação
- 1 = 2^0, então é uma potência de dois. Sua forma binária
1tem exatamente um bit 1.
+17 testes ocultos ao enviar
Para ir além
Com os mesmos truques de bits, você consegue testar se n é uma potência de quatro sem usar um loop?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Escreva algumas potências de dois em binário:
1,10,100,1000. O que todas elas têm em comum que 6 (110) não tem?Uma potência de dois tem exatamente um bit 1. Compare
ncomn-1em binário: subtrair 1 inverte o bit 1 mais baixo para 0 e cada 0 abaixo dele para 1.Assim,
né uma potência de dois exatamente quando é positivo e fazer AND entre ele en-1resulta em 0. Verifique o sinal antes dos bits, pois 0 e números negativos nunca são potências de dois.
Solução
Uma potência de dois tem uma forma fixa em binário: um bit 1 seguido de zeros, como 10000 para 16. Você pode confirmar essa forma dividindo n pela metade até que ele se torne ímpar, o que leva até 31 etapas. Ou pode confirmá-la em uma única etapa com n & (n-1), que zera o bit 1 menos significativo e deixa 0 apenas quando esse era o único bit. Nas duas versões, a verificação do sinal vem primeiro, porque zero e números negativos invalidam o código óbvio.
Divida por 2 enquanto o número for par
Intuição
Se n = 2^k, você pode dividi-lo por 2 exatamente k vezes e chegar a 1, e todos os valores nesse percurso são pares. Se n tiver um fator ímpar maior que 1, a divisão pela metade para em um número ímpar que não é 1. Para 16: 16, 8, 4, 2, 1; portanto, a resposta é verdadeira. Para 24: 24, 12, 6, 3, e 3 é ímpar, mas não é 1; portanto, a resposta é falsa.
Retorne false para n ≤ 0 antes do loop. Nenhuma potência de dois é zero ou negativa, e o loop nunca terminaria em 0, porque 0 é par e metade de 0 ainda é 0.
Cada etapa divide n pela metade, então uma entrada de 32 bits leva no máximo 31 etapas: tempo O(log n) e espaço O(1).
Algoritmo
- Se
n ≤ 0, retorne false. - Enquanto
nfor par, divida-o por 2. - Retorne se
nagora é 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Limpe o bit 1 menos significativo com n & (n-1)
Intuição
Escreva uma potência de dois em binário e ela será um único 1 seguido de zeros: 16 é 10000. Subtrair 1 transforma esse 1 em 0 e cada 0 abaixo dele em 1: 15 é 01111. Os dois números não compartilham nenhum bit 1, então 16 & 15 é 0.
Qualquer outro número positivo tem pelo menos dois bits 1. Subtrair 1 altera apenas o bit 1 mais baixo e os zeros abaixo dele, então cada bit 1 mais alto aparece nos dois números e o AND não é 0. Para 24, que é 11000, você obtém 23 = 10111, e 24 & 23 é 10000, que é 16.
Verifique n > 0 primeiro. 0 & -1 é 0 e, em aritmética de 32 bits, -2^31 é um único bit 1 seguido de 31 zeros, então o AND sozinho consideraria ambos potências de dois. O teste completo é uma comparação, uma subtração e um AND: tempo e espaço O(1). Lua 5.1 não tem operador AND, então o código em Lua monta o AND um bit de cada vez, em até 31 etapas para um n de 32 bits; o teste é o mesmo.
Algoritmo
- Se
n ≤ 0, retorne false. - Calcule
n & (n-1), que éncom seu bit 1 menos significativo zerado. - Retorne se esse resultado é 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
Armadilhas e casos extremos
O teste de bits ocupa uma linha, e a maioria dos erros está relacionada às entradas para as quais ele não foi projetado.
- Ignorar a verificação do sinal.
0 & (0-1)é 0, então 0 passa no teste AND. Com inteiros de 32 bits,-2^31também passa, porque sua forma binária é um único bit 1. Ambos devem retornar false. - Executar o loop de divisão por dois com 0. Zero é par, e dividi-lo por dois resulta novamente em 0, então o loop nunca termina.
- Remover os parênteses.
==tem precedência maior que&, então, em C, C++ e JavaScript,n & n - 1 == 0é interpretado comon & ((n - 1) == 0)e produz a resposta errada sem nenhum erro; Java e C# rejeitam isso como um erro de tipo. Escreva(n & (n - 1)) == 0. - Usar logaritmos. Em precisão dupla,
log(536870912) / log(2)resulta em 29.000000000000004, em vez de 29, então uma verificação de número inteiro considera2^29falso.
Perguntas frequentes4
Como verificar se um número é uma potência de dois?
Retorne true quando n > 0 e n & (n-1) for igual a 0. Uma potência de dois tem exatamente um bit 1, e subtrair 1 o limpa enquanto define apenas os bits abaixo dele, então o AND é 0. Sem operações bit a bit, divida n por dois enquanto ele for par e verifique se o resultado final é 1.
Por que n & (n-1) limpa o bit definido menos significativo?
Subtrair 1 pega emprestado do bit 1 menos significativo: esse bit se torna 0 e cada 0 abaixo dele se torna 1, enquanto os bits mais significativos permanecem iguais. Fazer AND com o valor original mantém apenas os bits definidos em ambos, que são exatamente os bits mais significativos. Para uma potência de dois, não há bits mais significativos, então o resultado é 0.
Qual é a complexidade de tempo de Potência de Dois?
A verificação n & (n-1) é executada em tempo e espaço O(1): uma comparação, uma subtração e um AND. O loop de divisão pela metade é executado em tempo O(log n), em no máximo 31 etapas para um inteiro de 32 bits.
1 é uma potência de dois? E 0?
1 é uma potência de dois, porque 2^0 = 1, e sua forma binária tem um bit 1. 0 não é: nenhum expoente inteiro resulta em 0, e ele não tem nenhum bit 1. Números negativos também nunca são potências de dois.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def isPowerOfTwo(n):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
n = 16
Esperado
true