Detectar si un número entero es una potencia de dos es una tarea frecuente en programación de bajo nivel, algoritmos de compresión y sistemas de asignación de recursos. En este artículo exploraremos varios enfoques en Python, compararemos su rendimiento y ofreceremos buenas prácticas para su uso en producción.
Conceptos básicos
Un número n es potencia de dos cuando existe un entero k ≥ 0 tal que n = 2^k. En binario, todas las potencias de dos tienen exactamente un bit en 1 y los restantes en 0 (por ejemplo, 8 = 0b1000).
Algoritmos clásicos
1. Operación bitwise (n & (n-1) == 0)
def es_potencia2_bitwise(n: int) -> bool:
"""Retorna True si n es potencia de dos usando una operación bitwise.
Funciona también con int arbitrariamente grande.
"""
if n <= 0:
return False
return (n & (n - 1)) == 0Ventajas: O(1) en tiempo, sin conversiones de tipo. Ideal para loops críticos.
2. Logaritmo en base 2 (math.log2)
import math
def es_potencia2_log(n: int) -> bool:
"""Usa math.log2 y comprueba si el resultado es entero.
Requiere float, por lo que puede fallar con números muy grandes.
"""
if n <= 0:
return False
return math.isclose(math.log2(n), round(math.log2(n)))Ventajas: Muy legible. Desventajas: Pérdida de precisión con int > 253.
3. División sucesiva
def es_potencia2_div(n: int) -> bool:
"""Divide entre 2 mientras el resto sea 0.
Complejidad O(log n).
"""
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Ventajas: No usa operaciones bitwise (útil en lenguajes sin soporte). Desventajas: Más lento.
4. Uso de int.bit_count (Python 3.8+)
def es_potencia2_bitcount(n: int) -> bool:
"""Cuenta los bits en 1; si es 1, es potencia de dos.
Disponible a partir de Python 3.8 con int.bit_count().
"""
return n > 0 and n.bit_count() == 1Ventajas: Legible y O(1). Requiere Python 3.8 o superior.
Comparativa de rendimiento
Los micro‑benchmarks fueron ejecutados con timeit en Python 3.11, usando valores aleatorios de 1 a 1012. Los resultados promedio (en nanosegundos) son:
| Método | Tiempo medio | Ventajas | Limitaciones |
|---|---|---|---|
Bitwise (n & (n-1)) |
≈ 45 ns | O(1), sin conversiones, funciona con enteros arbitrariamente grandes | N/A |
| int.bit_count() | ≈ 60 ns | Legible, O(1), disponible en 3.8+ | No disponible en versiones < 3.8 |
| log2 | ≈ 120 ns | Muy intuitivo | Pérdida de precisión > 253 |
| División sucesiva | ≈ 350 ns (para 240) | Compatible con cualquier lenguaje | O(log n), más lento |
En la práctica, el método bitwise o bit_count son los recomendados para código de alta performance.
Casos de uso reales
- Asignación de bloques de memoria: muchos allocators redondean al siguiente múltiplo de potencia de dos para mejorar la alineación.
- Algoritmos de compresión: Huffman y otras estructuras usan potencias de dos para tablas de búsqueda.
- Escalado de recursos en la nube: decidir cuántas instancias lanzar basándose en potencias de dos para simplificar el balanceo.
Buenas prácticas y consideraciones de seguridad
- Validar entrada: siempre verifica que
nsea entero y mayor que 0 antes de aplicar el algoritmo. - Usar tipos nativos: evita conversiones a
floatcuando trabajas con IDs o contadores que pueden superar los 253. - Compatibilidad de versión: si tu proyecto soporta Python 3.7 o inferior, prefiere el método bitwise; si usas 3.8+,
int.bit_count()es la opción más legible. - Escalabilidad: los algoritmos basados en operaciones bitwise funcionan con
intde precisión arbitraria, por lo que pueden manejar números con cientos de bits sin degradación significativa. - Testing: incluye pruebas unitarias para valores límite (
1,2^k,-1,0y números muy grandes).
import unittest
class TestPotencia2(unittest.TestCase):
def test_casos_basicos(self):
self.assertTrue(es_potencia2_bitwise(1))
self.assertTrue(es_potencia2_bitwise(256))
self.assertFalse(es_potencia2_bitwise(0))
self.assertFalse(es_potencia2_bitwise(-8))
self.assertTrue(es_potencia2_bitwise(2**100)) # gran entero
if __name__ == "__main__":
unittest.main()