Comprobar potencia de cuatro
La misión
Problema
Dado un número entero n que cabe en un entero con signo de 32 bits, devuelve True si n es igual a 4 elevado a algún exponente entero (1, 4, 16, 64, etc.) y False en caso contrario. El cero y los números negativos nunca son potencias de cuatro. Intenta responder sin un bucle, usando solo operaciones de bits.
Ejemplos
Input: n = 16
Output: True
Por qué: 16 es 4 al cuadrado
Input: n = 8
Output: False
Por qué: 8 es potencia de dos, pero su único bit encendido está en el lugar equivocado
Input: n = 1
Output: True
Por qué: caso límite: 4 elevado a 0 es 1
Pistas
0 / 3
Toda potencia de cuatro también es potencia de dos. Empieza por recordar cómo se ve una potencia de dos en binario.
Una potencia de dos tiene exactamente un bit encendido, y n & (n - 1) lo borra. ¿Qué más se cumple sobre la posición de ese bit en 1, 4, 16 y 64?
El único bit de una potencia de cuatro siempre cae en una posición par: 0, 2, 4, etc. Comprueba que n sea positivo, que tenga un solo bit encendido y que una máscara con un 1 en cada posición par conserve ese bit.
- Tiempo objetivo
- O(1)
- Espacio objetivo
- O(1)
Restricciones
- n fits in a signed 32-bit integer
Solución
Una potencia de cuatro es una potencia de dos cuyo único bit encendido está en una posición par, ya que cada multiplicación por cuatro desplaza ese bit dos lugares a la izquierda. Restar uno a una potencia de dos invierte su único bit y todos los bits que están debajo, así que n & (n - 1) es cero justamente en las potencias de dos. La máscara 0x55555555 tiene un 1 en cada posición par de una palabra de 32 bits, así que conserva el bit de 1, 4, 16 y 64 pero descarta el de 2, 8 y 32. El tiempo y el espacio son 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)) # -> False¿Lo que te frena es la idea y no el código? Máscaras y potencias de dos lo explica.