Power of Two
Recibes un número entero n. Devuelve true si n es una potencia de dos, es decir, n = 2^k para algún número entero k ≥ 0, y false en caso contrario. Así que 1, 2, 4 y 8 cuentan, mientras que 0, 6 y todos los números negativos no.
Función
- ninteger
- el entero que se va a probar, que puede ser cero o negativo
- Devuelveboolean
- true si n es igual a 2^k para algún k ≥ 0; false en caso contrario
Restricciones
-231 ≤ n ≤ 231-1
Ejemplos
- Entrada
- n = 16
- Salida
- true
- Explicación
- 16 = 2 × 2 × 2 × 2 = 2^4. En binario es
10000, un único bit 1.
- Entrada
- n = 24
- Salida
- false
- Explicación
- 24 = 8 × 3. Al dividir por la mitad se obtiene 12, 6 y después 3, que es impar pero no es 1. En binario, 24 es
11000, dos bits 1.
- Entrada
- n = 1
- Salida
- true
- Explicación
- 1 = 2^0, así que es una potencia de dos. Su forma binaria
1tiene exactamente un bit 1.
+17 pruebas ocultas al enviar
Para ir más allá
Con los mismos trucos de bits, ¿puedes comprobar si n es una potencia de cuatro sin usar un bucle?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Escribe algunas potencias de dos en binario:
1,10,100,1000. ¿Qué tienen todas en común que no tenga el 6 (110)?Una potencia de dos tiene exactamente un bit 1. Compara
nconn-1en binario: al restar 1, el bit 1 menos significativo cambia a 0 y cada 0 por debajo de él cambia a 1.Así que
nes una potencia de dos exactamente cuando es positivo y al aplicar AND conn-1se obtiene 0. Comprueba el signo antes que los bits, ya que 0 y los números negativos nunca son potencias de dos.
Solución
Una potencia de dos tiene una forma fija en binario: un bit 1 seguido de ceros, como 10000 para 16. Puedes confirmar esa forma dividiendo n entre dos hasta que se vuelva impar, lo que puede tomar hasta 31 pasos. O puedes confirmarla en un solo paso con n & (n-1), que borra el bit 1 menos significativo y deja 0 solo cuando ese bit era el único. En ambas versiones, primero se comprueba el signo, porque los números cero y negativos hacen que el código obvio falle.
Divide entre 2 mientras el número sea par
Intuición
Si n = 2^k, puedes dividirlo exactamente entre 2 k veces y llegar a 1, y todos los valores del camino son pares. Si n tiene un factor impar mayor que 1, el proceso de dividir entre 2 se detiene en un número impar que no es 1. Para 16: 16, 8, 4, 2, 1, así que la respuesta es verdadera. Para 24: 24, 12, 6, 3, y 3 es impar pero no es 1, así que la respuesta es falsa.
Devuelve false para n ≤ 0 antes del bucle. Ninguna potencia de dos es cero o negativa, y el bucle nunca terminaría con 0, porque 0 es par y la mitad de 0 sigue siendo 0.
Cada paso divide n entre 2, así que una entrada de 32 bits requiere como máximo 31 pasos: tiempo O(log n) y espacio O(1).
Algoritmo
- Si
n ≤ 0, devuelve false. - Mientras
nsea par, divídelo entre 2. - Devuelve si
nahora es 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Elimina el bit menos significativo establecido con n & (n-1)
Intuición
Escribe una potencia de dos en binario y tendrás un único 1 seguido de ceros: 16 es 10000. Restar 1 convierte ese 1 en 0 y todos los ceros que hay debajo en 1: 15 es 01111. Los dos números no comparten ningún bit 1, así que 16 & 15 es 0.
Cualquier otro número positivo tiene al menos dos bits 1. Restar 1 cambia solo el bit 1 más bajo y los ceros que hay debajo, así que todos los bits 1 más altos aparecen en ambos números y el AND no es 0. Para 24, que es 11000, obtienes 23 = 10111, y 24 & 23 es 10000, que es 16.
Comprueba primero n > 0. 0 & -1 es 0, y en la aritmética de 32 bits -2^31 es un único bit 1 seguido de 31 ceros, así que el AND por sí solo consideraría que ambos son potencias de dos. La prueba completa consta de una comparación, una resta y un AND: tiempo y espacio O(1). Lua 5.1 no tiene un operador AND, así que el código Lua construye el AND bit a bit, en hasta 31 pasos para un n de 32 bits; la prueba es la misma.
Algoritmo
- Si
n ≤ 0, devuelve false. - Calcula
n & (n-1), que esncon su bit 1 menos significativo borrado. - Devuelve si ese resultado es 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
Errores comunes y casos límite
La prueba de bits ocupa una línea, y la mayoría de los errores tienen que ver con las entradas para las que no fue diseñada.
- Omitir la comprobación del signo.
0 & (0-1)es 0, así que 0 pasa la prueba AND. Con enteros de 32 bits,-2^31también pasa, porque su forma binaria es un único bit 1. Ambos deben devolver false. - Ejecutar el bucle de división por la mitad con 0. Cero es par, y dividirlo por la mitad vuelve a dar 0, así que el bucle nunca termina.
- Omitir los paréntesis.
==tiene mayor precedencia que&, así que en C, C++ y JavaScriptn & n - 1 == 0se interpreta comon & ((n - 1) == 0)y da una respuesta incorrecta sin ningún error; Java y C# lo rechazan por un error de tipo. Escribe(n & (n - 1)) == 0. - Usar logaritmos. En precisión doble,
log(536870912) / log(2)da 29.000000000000004 en lugar de 29, así que una comprobación de número entero considera falso2^29.
Preguntas frecuentes4
¿Cómo compruebas si un número es una potencia de dos?
Devuelve true cuando n > 0 y n & (n-1) sea igual a 0. Una potencia de dos tiene exactamente un bit 1, y al restar 1 se borra ese bit y se establecen solo los bits inferiores, por lo que el AND es 0. Sin operaciones bit a bit, divide n entre dos mientras sea par y comprueba que terminas en 1.
¿Por qué n & (n-1) borra el bit activado de menor peso?
Al restar 1, se toma prestado del bit 1 menos significativo: ese bit pasa a ser 0 y cada 0 que está por debajo se convierte en 1, mientras que los bits superiores permanecen iguales. Al aplicar AND con el valor original, solo se conservan los bits activados en ambos, que son exactamente los bits superiores. En una potencia de dos no hay bits superiores, así que el resultado es 0.
¿Cuál es la complejidad temporal de Power of Two?
La comprobación n & (n-1) se ejecuta en tiempo y espacio O(1): una comparación, una resta y una operación AND. El bucle de división por la mitad se ejecuta en tiempo O(log n), con un máximo de 31 pasos para un entero de 32 bits.
¿Es 1 una potencia de dos? ¿Y 0?
1 es una potencia de dos, porque 2^0 = 1 y su forma binaria tiene un bit 1. 0 no lo es: ningún exponente entero da 0 y no tiene ningún bit 1. Los números negativos tampoco son nunca potencias de dos.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def isPowerOfTwo(n):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
n = 16
Esperado
true