Verificar potência de quatro
A missão
Problema
Dado um número inteiro n que cabe num inteiro de 32 bits com sinal, retorne True se n for igual a 4 elevado a algum expoente inteiro (1, 4, 16, 64 e assim por diante) e False caso contrário. Zero e números negativos nunca são potências de quatro. Tente responder sem um loop, usando só operações bit a bit.
Exemplos
Input: n = 16
Output: True
Por quê: 16 é 4 ao quadrado
Input: n = 8
Output: False
Por quê: 8 é uma potência de dois, mas o seu único bit ligado está no lugar errado
Input: n = 1
Output: True
Por quê: edge case: 4 elevado a 0 é 1
Dicas
0 / 3
Toda potência de quatro também é uma potência de dois. Comece lembrando como uma potência de dois aparece em binário.
Uma potência de dois tem exatamente um bit ligado (set bit), e n & (n - 1) o zera. O que mais é verdade sobre a posição desse bit no 1, no 4, no 16 e no 64?
O único bit de uma potência de quatro sempre cai numa posição par: 0, 2, 4 e assim por diante. Verifique se n é positivo, se tem um único bit ligado e se uma máscara com 1 em toda posição par mantém esse bit.
- Tempo-alvo
- O(1)
- Espaço-alvo
- O(1)
Restrições
- n fits in a signed 32-bit integer
Solução
Uma potência de quatro é uma potência de dois cujo único bit ligado fica numa posição par, já que cada multiplicação por quatro desloca esse bit duas posições para a esquerda. Subtrair um de uma potência de dois inverte o seu único bit e todos os bits abaixo dele, então n & (n - 1) é zero exatamente para as potências de dois. A máscara 0x55555555 tem 1 em toda posição par de uma palavra de 32 bits; assim, ela mantém o bit de 1, 4, 16 e 64, mas descarta o bit de 2, 8 e 32. O tempo e o espaço são O(1).
def is_power_of_four(n):
one_bit = n > 0 and (n & (n - 1)) == 0 # a power of two has a single set bit
return one_bit and (n & 0x55555555) != 0 # ...and for four it sits at an even position
print(is_power_of_four(16)) # -> True
print(is_power_of_four(8)) # -> False
print(is_power_of_four(1)) # -> True
print(is_power_of_four(0)) # -> FalseTravou na ideia, e não no código? Máscaras e potência de dois explica isso.